Busca binária em JavaScript: versões iterativa e recursiva, array ordenado e complexidade O(log n). Fechamento da série com código.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
Buscar 42 num array de 1 milhão de posições um a um é lento. Com array , corta o espaço pela metade a cada passo — O(log n).
O que você vai aprender:
(lo + hi) >>> 1 no meioPré-requisitos: ordenação (ep. 15) e arrays (ep. 2).
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.
scene: en/data-structures-in-a-nutshell/binary-search-steps
Interactive Excalidraw view is not available in this build.
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.
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.
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:
lo no início e hi no fim do array.mid.sorted[mid] é nosso alvo, retorna o índice imediatamente.sorted[mid], ele deve estar na metade direita—move lo pra depois de mid.hi pra antes de mid.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.jsResultado 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 -1As 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.
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 bisectgit 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.
Muitas linguagens implementam busca binária nas bibliotecas padrão:
Array.prototype.findIndex com comparador pode ser lento pra arrays grandes ordenados—uma busca binária customizada é muito mais rápida.bisect.bisect_left / bisect.bisect_rightArrays.binarySearchsort.SearchIntsBusca 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.
| Item | Detalhe |
|---|---|
| Pré-condição | Array ordenado |
| Tempo | O(log n) |
| Espaço iterativo | O(1) |
git bisect | Mesma ideia em commits |
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.
Receba notas de arquitetura e performance na sua caixa de entrada. Mesma lista do convite—inscreva-se aqui quando quiser.
