Algoritmo de Busca Binária em JavaScript: Pesquisas Rápidas em Arrays Ordenados

A busca binária divide progressivamente o array ao meio para localizar um elemento sem a necessidade de percorrer toda a lista sequencialmente. Essa abordagem resolve o gargalo de performance da busca linear em coleções de dados massivas, reduzindo o tempo de execução para escala logarítmica.

JavaScript

/**
 * Realiza a busca binária em um array ordenado.
 * @param {Array<number>} arr - Array ordenado de números.
 * @param {number} alvo - Valor a ser localizado.
 * @returns {number} Índice do elemento ou -1 se não for encontrado.
 */
function buscaBinaria(arr, alvo) {
  let inicio = 0;
  let fim = arr.length - 1;

  while (inicio <= fim) {
    // Math.floor garante um índice inteiro para o ponto médio
    const meio = Math.floor((inicio + fim) / 2);

    // Retorna o índice caso o valor seja encontrado
    if (arr[meio] === alvo) {
      return meio;
    }

    // Se o valor do meio for maior que o alvo, ajusta o limite superior
    if (arr[meio] > alvo) {
      fim = meio - 1;
    } else {
      // Caso contrário, ajusta o limite inferior
      inicio = meio + 1;
    }
  }

  // Retorna -1 se o elemento não estiver presente no array
  return -1;
}

// --- Exemplo Prático de Uso ---
const numerosOrdenados = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const itemProcurado = 23;

const indiceEncontrado = buscaBinaria(numerosOrdenados, itemProcurado);

if (indiceEncontrado !== -1) {
  console.log(`Elemento ${itemProcurado} encontrado no índice: ${indiceEncontrado}`);
} else {
  console.log(`Elemento ${itemProcurado} não existe no array.`);
}

Pontos-chave

• Precondição de Ordenação: Funciona apenas em arrays pré-ordenados; para arrays desordenados, utilize arr.sort((a, b) => a - b) antes de executar o algoritmo.
• Complexidade $O(\log n)$: Em um array com 1.000.000 de itens, o algoritmo encontra o valor em no máximo 20 comparações.
• Tratamento de Divisão em JS: O uso de Math.floor() é obrigatório, pois a divisão nativa do JavaScript produz números de ponto flutuante (floats).
• Retorno Padrão (0-based): Retorna o índice base zero do elemento localizado ou -1 para indicar ausência, facilitando verificações diretas no código.