Implementação de busca binária em JavaScript
Nível 5421 toques
binarySearch procura um valor em um array ordenado verificando o elemento do meio e dividindo o intervalo pela metade a cada passo. Imprime 3 para 7, -1 para 8 (ausente) e 0 para 1.
Código JavaScript
// Retorna o índice de target no array ordenado arr, ou -11function binarySearch(arr, target) { // O intervalo de busca começa sendo o array inteiro: índices 0 a length - 12 let left = 0;3 let right = arr.length - 1;4 // Repete enquanto o intervalo tiver pelo menos um elemento5 while (left <= right) { // Índice do elemento do meio, arredondado para baixo6 const mid = Math.floor((left + right) / 2);7 // O elemento do meio é target: retorna seu índice8 if (arr[mid] === target) return mid; // O meio é pequeno demais, então target só pode estar na metade direita9 if (arr[mid] < target) left = mid + 1; // O meio é grande demais, então a busca continua na metade esquerda10 else right = mid - 1;11 }12 // O intervalo ficou vazio: target não está no array13 return -1;14}15 // A busca binária só funciona em um array ordenado como este16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];// 7 é encontrado no primeiro meio, o índice 3, então imprime 317console.log(binarySearch(sorted, 7));// 8 não está no array, então imprime -118console.log(binarySearch(sorted, 8));// 1 é o primeiro elemento, então imprime 019console.log(binarySearch(sorted, 1));Saída
3 -1 0
Pratique digitando este código. Os resultados não são registrados no ranking.
Símbolos deste código
Os símbolos que você digita neste código JavaScript e quantas vezes aparecem.
(× 12)× 12,× 11;× 11=× 10.× 5-× 3[× 3]× 3{× 2