Implementando Busca Binária em JavaScript

Você está pesquisando em um array ordenado de 100.000 preços de produtos. O método nativo indexOf() do JavaScript verifica cada elemento desde o início — são potencialmente 100.000 comparações. A busca binária faz isso em no máximo 17. Essa diferença é o motivo pelo qual o algoritmo de busca binária em JavaScript é importante, e por que vale a pena escrevê-lo você mesmo — porque o JavaScript não fornece um método nativo de busca binária.

Este artigo aborda como a busca binária funciona, como implementar versões iterativas e recursivas, e quando usá-la em vez da busca linear.

O Que É Busca Binária e Por Que Ela Requer um Array Ordenado?

A busca binária é um algoritmo de divisão e conquista. Funciona dividindo repetidamente o espaço de busca pela metade até encontrar o valor alvo ou esgotar todas as possibilidades.

Aqui está o detalhe: funciona apenas em arrays ordenados. O algoritmo assume que se o alvo for maior que o elemento do meio, ele deve estar na metade direita. Essa suposição falha completamente em dados não ordenados — você obteria resultados errados sem nenhum erro.

Os passos são:

1. Encontrar o elemento do meio do intervalo de busca atual
2. Se for igual ao alvo, retornar seu índice
3. Se o alvo for menor, buscar na metade esquerda
4. Se o alvo for maior, buscar na metade direita
5. Repetir até encontrar ou o intervalo de busca ficar vazio

---

Implementando Busca Binária em JavaScript: Abordagem Iterativa

A versão iterativa usa um loop while e dois ponteiros. É a abordagem preferida para a maioria dos casos — legível, eficiente e usa espaço O(1).

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // Retorna o índice
    } else if (arr[mid] < target) {
      start = mid + 1 // Busca na metade direita
    } else {
      end = mid - 1 // Busca na metade esquerda
    }
  }

  return -1 // Alvo não encontrado
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

Note que isso retorna o índice do alvo, não um booleano. Isso é quase sempre mais útil na prática.

---

Busca Binária Recursiva em JavaScript

A versão recursiva passa índices de limite atualizados em cada chamada. É elegante, mas usa espaço de pilha O(log n) — um frame por chamada recursiva.

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

Um bug comum: esquecer de usar return na chamada recursiva. Sem ele, a função retorna undefined mesmo quando o elemento existe.

---

Ordenando Antes de Buscar

Se seu array ainda não estiver ordenado, você precisa ordená-lo primeiro. O Array.sort() padrão do JavaScript ordena lexicograficamente, o que quebra comparações numéricas:

[10, 9, 100].sort()                   // [10, 100, 9] — errado
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — correto

Sempre use um comparador numérico para arrays de números antes de executar a busca binária.

---

Busca Binária vs Busca Linear: Quando Usar Cada Uma

Para um array de 10.000 elementos, a busca linear precisa de até 10.000 comparações. A busca binária precisa de no máximo 14. Se você está buscando uma vez em um array pequeno e não ordenado, indexOf() está bom. Se você está buscando repetidamente em dados ordenados grandes, a busca binária é a ferramenta certa.

---

Conclusão

A busca binária é simples de implementar em JavaScript uma vez que você entende o requisito de array ordenado. Use a versão iterativa por padrão — é mais limpa e evita sobrecarga da pilha de chamadas. Use a versão recursiva quando a estrutura do seu código se beneficiar disso, mas lembre-se de sempre usar return na chamada recursiva. E sempre verifique se seu array está ordenado com um comparador numérico adequado antes de buscar.

Perguntas Frequentes

A busca binária funciona com arrays de strings em JavaScript?

Sim, a busca binária funciona com arrays de strings desde que estejam ordenados alfabeticamente. Os operadores de comparação em JavaScript lidam com comparação de strings lexicograficamente por padrão, então a mesma lógica do algoritmo se aplica. Apenas certifique-se de que o array está ordenado usando o método sort padrão, que já ordena strings em ordem lexicográfica.

Por que o JavaScript não tem um método nativo de busca binária?

Os arrays do JavaScript são projetados para serem flexíveis e podem conter tipos mistos, o que torna uma busca binária nativa impraticável, pois ela requer uma coleção ordenada e de tipo uniforme. Bibliotecas como Lodash fornecem sortedIndexOf para esse propósito, mas para JavaScript puro você precisa escrever sua própria implementação.

A busca binária pode lidar com valores duplicados em um array?

A implementação padrão retorna o índice de um elemento correspondente, mas não necessariamente a primeira ou última ocorrência. Se você precisar do primeiro ou último índice de um valor duplicado, deve modificar o algoritmo para continuar buscando na metade esquerda ou direita mesmo após encontrar uma correspondência.

A versão iterativa ou recursiva da busca binária é mais rápida em JavaScript?

Ambas têm a mesma complexidade de tempo O(log n), então sua velocidade bruta é quase idêntica. No entanto, a versão iterativa evita a sobrecarga de chamadas de função recursivas e usa memória constante, tornando-a ligeiramente mais eficiente na prática. Para recursões muito profundas, a versão recursiva também pode arriscar um estouro de pilha.