Pular para o conteúdo
</> Entendendo Algoritmos

Busca binária

Em um array ordenado de 1 até N, o algoritmo olha para o elemento do meio e descarta metade das opções a cada tentativa.

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
function buscaBinaria(lista, alvo) {
  let inicio = 0;
  let fim = lista.length - 1;

  while (inicio <= fim) {
    const meio = Math.floor((inicio + fim) / 2);

    if (lista[meio] === alvo) return meio;   // achou
    if (lista[meio] < alvo) inicio = meio + 1;   // descarta a metade esquerda
    else fim = meio - 1;                         // descarta a metade direita
  }

  return -1;   // não está na lista
}