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 -1
1function binarySearch(arr, target) {
// O intervalo de busca começa sendo o array inteiro: índices 0 a length - 1
2 let left = 0;
3 let right = arr.length - 1;
4
// Repete enquanto o intervalo tiver pelo menos um elemento
5 while (left <= right) {
// Índice do elemento do meio, arredondado para baixo
6 const mid = Math.floor((left + right) / 2);
7
// O elemento do meio é target: retorna seu índice
8 if (arr[mid] === target) return mid;
// O meio é pequeno demais, então target só pode estar na metade direita
9 if (arr[mid] < target) left = mid + 1;
// O meio é grande demais, então a busca continua na metade esquerda
10 else right = mid - 1;
11 }
12
// O intervalo ficou vazio: target não está no array
13 return -1;
14}
15
// A busca binária só funciona em um array ordenado como este
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 é encontrado no primeiro meio, o índice 3, então imprime 3
17console.log(binarySearch(sorted, 7));
// 8 não está no array, então imprime -1
18console.log(binarySearch(sorted, 8));
// 1 é o primeiro elemento, então imprime 0
19console.log(binarySearch(sorted, 1));

Saída

3
-1
0
Praticar digitando este código

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

Mais exemplos de JavaScript de nível 5

← Prática de digitação de JavaScript