Busca: busca linear e busca binária

Para achar um nome numa lista ordenada de um milhão, a busca binária nunca precisa de mais de 20 verificações.

Procurando um valor

Buscar é o problema de achar onde um valor está numa coleção, ou descobrir que ele não está lá. Seu celular faz isso quando você digita o nome de um contato, uma loja faz isso quando confere se um item está em estoque, e um corretor ortográfico faz isso para cada palavra que você digita. A entrada é uma lista e um valor-alvo. A saída é a posição do alvo, ou um sinal como -1, que quer dizer "não encontrado".

Busca linear: um de cada vez

O método mais simples é começar pela esquerda e verificar cada valor por vez, até achar o alvo ou acabar a lista. Isso é a busca linear. Ela funciona em qualquer lista, ordenada ou não. O custo depende da sorte: se o alvo é o primeiro, uma verificação basta; se é o último ou não está lá, você verifica todos os valores. Para uma lista de n valores, o pior caso é n verificações. Uma lista com o dobro do tamanho pode levar o dobro de verificações, e é daí que vem o nome "linear": o trabalho cresce em linha reta com o tamanho.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // achou
  }
  return -1;                             // verificou tudo
}

Busca binária: corte pela metade o que sobra

Se a lista está ordenada, dá para fazer muito melhor. Pense no jogo de adivinhar números: alguém escolhe um número de 1 a 100 e só responde "maior" ou "menor". Um jogador esperto chuta 50 primeiro. Seja qual for a resposta, metade das possibilidades some. O próximo chute é o meio do que sobrou, e assim por diante. A busca binária faz exatamente isso com uma lista ordenada. Ela mantém dois marcadores, lo e hi, em volta da parte em que o alvo ainda pode estar. Ela verifica o valor do meio. Se for o alvo, acabou. Se o valor do meio for menor que o alvo, tudo à esquerda dele também é menor, então lo passa para depois do meio. Se for maior, hi passa para antes do meio. Quando lo ultrapassa hi, não sobra nada e o alvo não está na lista.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // o alvo está à direita
    else hi = mid - 1;                     // o alvo está à esquerda
  }
  return -1;
}

Quantas verificações?

Cada verificação da busca binária corta pelo menos pela metade a parte que sobra. Partindo de n valores, depois de uma verificação sobram no máximo cerca de n/2, depois de duas cerca de n/4, e assim por diante até sobrar um valor. O número de cortes pela metade necessários para ir de n até 1 é o logaritmo de n na base 2, escrito log₂ n. Contando também a verificação final, a busca binária precisa de no máximo ⌊log₂ n⌋ + 1 verificações, em que ⌊ ⌋ quer dizer arredondar para baixo. Para 100 valores isso dá 7 verificações, e é por isso que o jogo de adivinhar sempre pode ser vencido em 7 chutes. Para 1000 valores são 10, para um milhão 20 e para um bilhão 30.

O porém: a lista precisa estar ordenada

A busca binária só funciona porque, numa lista ordenada, uma comparação diz de que lado o alvo tem de estar. Numa lista desordenada, o valor do meio não diz nada sobre os vizinhos, e você volta à busca linear. Ordenar dá trabalho também (as duas próximas unidades tratam disso), então a escolha depende do uso. Se você vai buscar numa lista uma vez só, uma busca linear pode sair mais barata. Se vai buscar na mesma lista milhares de vezes, ordená-la uma vez e depois usar a busca binária compensa rápido. Essa troca entre preparar os dados e responder perguntas sobre eles atravessa a matéria inteira.