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

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.