Busca binária

A ideia

Pense num jogo: eu escolho um número de 1 a 100 e você tenta adivinhar. A cada chute eu digo “é maior” ou “é menor”. Começar pelo 1 e subir de um em um funciona, mas pode levar 100 chutes. Chutar 50 elimina metade das opções de uma vez. Depois 25 ou 75, e assim por diante. Em no máximo 7 chutes você acerta.

A busca binária faz exatamente isso num array ordenado. Ela mantém um intervalo [low, high] onde o alvo ainda pode estar e, a cada passo, olha o elemento do meio:

Se for o alvo, acabou.
Se for menor que o alvo, o alvo só pode estar à direita: low = mid + 1.
Se for maior, só pode estar à esquerda: high = mid - 1.

Veja rodando

Observe os ponteiros low, mid e high e como os elementos descartados vão apagando.

0low

9high

O array está ordenado. A busca começa com o intervalo inteiro: low = 0, high = 9.

function binarySearch(array: number[], target: number): number {
  let low = 0
  let high = array.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)

    if (array[mid] === target) {
      return mid
    } else if (array[mid] < target) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }

  return -1
}

target: 23
low: 0
high: 9

Agora você prevê

Antes de cada passo, clique no índice do meio que a busca vai examinar. Dica: mid = Math.floor((low + high) / 2). Este alvo não existe; quando o intervalo ficar vazio, escolha Nenhum.

0low

11high

Sua vez: clique no índice que o algoritmo vai examinar agora.

O array está ordenado. A busca começa com o intervalo inteiro: low = 0, high = 11.

function binarySearch(array: number[], target: number): number {
  let low = 0
  let high = array.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)

    if (array[mid] === target) {
      return mid
    } else if (array[mid] < target) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }

  return -1
}

target: 50
low: 0
high: 11

O invariante

O segredo para escrever uma busca binária sem erro é saber o que nunca muda durante o loop:

Se o alvo está no array, ele está entre low e high (inclusive).

Toda atualização preserva isso. low = mid + 1 só acontece quando array[mid] < target, então nada à esquerda de mid + 1 pode ser o alvo. Quando low > high, o intervalo está vazio e o invariante garante que o alvo não existe.

Os erros mais comuns quebram justamente esse invariante:

while (low < high) em vez de <=: deixa de examinar o último elemento que sobrou.
low = mid em vez de mid + 1: o intervalo pode parar de diminuir e virar um loop infinito.

Custo

Cada passo corta o intervalo pela metade. Começando com n elementos, depois de k passos sobram n / 2^k. Isso chega a 1 quando k = log₂ n.

n	Busca linear (pior caso)	Busca binária (pior caso)
100	100	7
1.000.000	1.000.000	20
1.000.000.000	1.000.000.000	30

Tempo O(log n), memória extra O(1).

Onde ela aparece

git bisect acha o commit que introduziu um bug fazendo busca binária no histórico.
Índices de banco de dados (árvores B) aplicam a mesma ideia para achar uma linha entre milhões.
_.sortedIndex do Lodash e bisect do Python encontram onde inserir um valor mantendo a ordem.
Fora de arrays: “qual o menor tamanho de lote que não estoura a memória?” também se resolve dividindo o intervalo de respostas ao meio.

Teste sua memória

Quantas comparações, no máximo, a busca binária faz num array ordenado com 1.000 elementos?101005001.000

Com low = 4 e high = 9, qual índice a busca examina?4679

Qual troca transforma a busca binária num possível loop infinito?high = mid - 1 por high = mid + 1low = mid + 1 por low = midMath.floor por Math.trunc

Pronto para praticar? Comece pelo livro da biblioteca.