Busca linear e binária

Busca

Busca linear — O(n)

Percorre o array elemento por elemento até encontrar o objetivo. Funciona com qualquer array, ordenado ou não.

function buscaLinear(arr, objetivo) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === objetivo) return i;
  }
  return -1;
}

Busca binária — O(log n)

Muito mais rápida, mas exige um array ordenado. A ideia: olhar o meio e descartar a metade que não pode conter o objetivo, repetindo.

function buscaBinaria(arr, objetivo) {
  let inicio = 0;
  let fim = arr.length - 1;
  while (inicio <= fim) {
    const meio = Math.floor((inicio + fim) / 2);
    if (arr[meio] === objetivo) return meio;
    if (arr[meio] < objetivo) inicio = meio + 1;
    else fim = meio - 1;
  }
  return -1;
}

Com um milhão de elementos, a busca linear pode fazer um milhão de comparações; a binária, apenas umas 20.

Exemplos

Busca binária passo a passo

function buscaBinaria(arr, objetivo) {
  let inicio = 0, fim = arr.length - 1;
  while (inicio <= fim) {
    const meio = Math.floor((inicio + fim) / 2);
    console.log("Verifico índice", meio, "valor", arr[meio]);
    if (arr[meio] === objetivo) return meio;
    if (arr[meio] < objetivo) inicio = meio + 1;
    else fim = meio - 1;
  }
  return -1;
}
console.log("Encontrado em:", buscaBinaria([1, 3, 5, 7, 9, 11], 9));