Implementando Busca Binária com NodeJS e Javascript

Buscar 42 num array de 1 milhão de posições um a um é lento. Com array ordenado, busca binária corta o espaço pela metade a cada passo — O(log n).

O que você vai aprender:

• Versão iterativa e recursiva
• Por que (lo + hi) >>> 1 no meio
• Retornar índice ou -1
• Generalizar para “primeiro true em sequência monótona”

Pré-requisitos: ordenação (ep. 15) e arrays (ep. 2).

Busca binária: dividir o array ordenado

Chegamos ao Post 16—o post final do Data Structures in a Nutshell. E a gente tá encerrando com um dos algoritmos mais elegantes da ciência da computação: busca binária.

Você usou busca binária indiretamente ao longo de toda essa série. BSTs usam a mesma lógica de "vai pra esquerda se menor, pra direita se maior". Heaps usam intuição similar de dividir e conquistar. Agora vamos ver diretamente num array ordenado.

A ideia é simplesíssima: dado um array ordenado e um valor alvo, verifica o elemento do meio. Se for o alvo, acabou. Se o alvo for menor, joga fora a metade direita. Se for maior, joga fora a metade esquerda. Repete até achar ou não sobrar nada.

graph LR
  step1["[1, 3, 5, 7, 9, 11, 13]\nlo=0, hi=6, mid=3 → arr[3]=7\nAlvo 5 < 7 → hi=2"]
  step2["[1, 3, 5, ...]\nlo=0, hi=2, mid=1 → arr[1]=3\nAlvo 5 > 3 → lo=2"]
  step3["[..., 5, ...]\nlo=2, hi=2, mid=2 → arr[2]=5\nAchou! retorna 2"]
  step1 --> step2 --> step3

Cada passo corta o espaço de busca pela metade. Pra um array de 1 bilhão de elementos, são no máximo 30 comparações pra achar qualquer valor. Compara isso com varrer até 1 bilhão de itens linearmente—é O(log n) vs O(n) e a diferença é enorme.

Mão na Massa

Um Pouco Mais de Teoria

Busca binária tem um requisito rígido: o array deve estar ordenado. Esse é o contrato. Se o array estiver desordenado, a busca binária dá resultados errados silenciosamente—não vai dar erro, vai só perder coisas.

A outra sutileza é o cálculo do ponto médio. O ingênuo (lo + hi) / 2 pode causar overflow quando lo e hi são inteiros grandes (importa mais em linguagens com inteiros de tamanho fixo como Java ou C, mas é um bom hábito). A versão segura é (lo + hi) >>> 1, que usa um shift à direita sem sinal pra dividir a soma ao meio sem overflow.

Agora a Prática

Cria um arquivo chamado binary-search.js e cola o código abaixo:

// Iterativa — a versão que você vai usar em produção
function binarySearch(sorted, target) {
  let lo = 0
  let hi = sorted.length - 1
 
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1
 
    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
 
  return -1 // não encontrado
}

Explicando:

• Começamos com lo no início e hi no fim do array.
• Cada iteração calcula o ponto médio mid.
• Se sorted[mid] é nosso alvo, retorna o índice imediatamente.
• Se o alvo é maior que sorted[mid], ele deve estar na metade direita—move lo pra depois de mid.
• Se o alvo é menor, ele deve estar na metade esquerda—move hi pra antes de mid.
• Se lo ultrapassar hi, esgotamos o espaço de busca—retorna -1.

Agora vamos adicionar a versão recursiva também, já que é uma pergunta comum em entrevistas e mostra a mesma lógica de um ângulo diferente:

// Recursiva — elegante, mas cuidado com arrays muito grandes (profundidade de pilha)
function binarySearchRecursive(sorted, target, lo = 0, hi = sorted.length - 1) {
  if (lo > hi) return -1
 
  const mid = (lo + hi) >>> 1
 
  if (sorted[mid] === target) return mid
  if (sorted[mid] < target) return binarySearchRecursive(sorted, target, mid + 1, hi)
  return binarySearchRecursive(sorted, target, lo, mid - 1)
}

Vamos testar os dois. Depois das funções, adiciona:

const sorted = [1, 3, 5, 7, 9, 11, 13, 17, 21, 25]
 
console.log('Array:', sorted)
console.log()
 
// Iterativa
console.log('binarySearch(sorted, 7)  → índice', binarySearch(sorted, 7))
console.log('binarySearch(sorted, 1)  → índice', binarySearch(sorted, 1))
console.log('binarySearch(sorted, 25) → índice', binarySearch(sorted, 25))
console.log('binarySearch(sorted, 6)  → índice', binarySearch(sorted, 6))
console.log()
 
// Recursiva
console.log('binarySearchRecursive(sorted, 13) → índice', binarySearchRecursive(sorted, 13))
console.log('binarySearchRecursive(sorted, 99) → índice', binarySearchRecursive(sorted, 99))

Roda:

node binary-search.js

Resultado esperado:

Array: [
   1,  3,  5,  7,  9,
  11, 13, 17, 21, 25
]
 
binarySearch(sorted, 7)  → índice 3
binarySearch(sorted, 1)  → índice 0
binarySearch(sorted, 25) → índice 9
binarySearch(sorted, 6)  → índice -1
 
binarySearchRecursive(sorted, 13) → índice 6
binarySearchRecursive(sorted, 99) → índice -1

As duas implementações retornam o índice correto pra valores que existem e -1 pra valores que não existem.

Jon, e se tiver valores duplicados no array?

Boa observação. A busca binária padrão acha um índice que bate, mas não necessariamente o primeiro ou o último. Se você precisar da ocorrência mais à esquerda ou mais à direita, continua buscando depois de achar uma correspondência em vez de retornar imediatamente. Isso se chama busca de lower bound ou upper bound—vale conhecer pra entrevistas.

Aonde Você Pode Usar/Ver

Buscas em Índices de Banco de Dados

Quando um banco de dados faz uma varredura de índice B-Tree, o lookup em cada nó é essencialmente uma busca binária sobre as chaves ordenadas armazenadas ali. Sem ordenação, índices não funcionariam.

git bisect

git bisect é literalmente busca binária aplicada ao histórico de commits. Você diz pro Git "esse commit é bom, esse é ruim" e ele faz checkout do commit do meio pra você testar—cortando o espaço de busca pela metade a cada passo até encontrar o primeiro commit ruim. Elegante demais.

Funções de Biblioteca Padrão

Muitas linguagens implementam busca binária nas bibliotecas padrão:

• JavaScript: sem busca binária nativa, mas Array.prototype.findIndex com comparador pode ser lento pra arrays grandes ordenados—uma busca binária customizada é muito mais rápida.
• Python: bisect.bisect_left / bisect.bisect_right
• Java: Arrays.binarySearch
• Go: sort.SearchInts

Edge cases: array desordenado e off-by-one

Busca binária em array não ordenado não explode — retorna lixo silencioso. Ordene antes ou use Map.

Condição de loop: lo <= hi (iterativa). Esquecer mid + 1 / mid - 1 causa loop infinito.

TL;DR — Busca binária

Próximos passos

• Fechamento da série: Resumo das estruturas
• Módulos Node: require e exports

Antes de fechar

Fim da série Data Structures in a Nutshell — 16 episódios. Qual post mais te ajudou? Se viu erro em algum código da série, comenta que corrigimos juntos.