A busca binária é um eficiente algoritmo para encontrar um item em uma lista ordenada de itens. Ela funciona dividindo repetidamente pela metade a porção da lista que deve conter o item, até reduzir as localizações possíveis a apenas uma. Nós usamos a busca binária em um jogo de adivinhação no tutorial introdutório.
Um dos modos mais comuns de se usar a busca binária é para encontrar um item em um array. Por exemplo, o catálogo estelar Tycho-2 contém informações sobre as 2.539.913 estrelas mais brilhantes na nossa galáxia. Suponha que você queira buscar por uma estrela em particular no catálogo, com base no nome da estrela. Se o programa examinou cada estrela do catálogo de estrelas em ordem começando com o primeiro nome, utilizando um algoritmo chamado busca linear, no pior caso, o computador pode ter examinado todas as 2,539,913 estrelas para encontrar a estrela que você está procurando. Se o catálogo estivesse organizado alfabeticamente pelos nomes das estrelas, a busca binária não teria que examinar mais do que 22 estrelas, mesmo no pior caso.
Os próximos artigos discutem como descrever o algoritmo cuidadosamente, como implementá-lo em JavaScript e como analisar sua eficiência.

Pseudocódigo para busca binária

Quando descrevemos um algoritmo para outro ser humano, uma descrição incompleta muitas vezes é o bastante. Alguns detalhes podem ter ficado de fora de um recipiente para um bolo; o recipiente assume que você sabe como abrir o refrigerador para pegar os ovos e que você sabe como quebrar os ovos. As pessoas podem intuitivamente saber como encontrar detalhes faltantes, mas os programas de computador não podem. É por isso que precisamos descrever completamente os algoritmos de computador.
Para implementar um algoritmo em uma linguagem de programação, você precisa entender todos os detalhes do algoritmo. Quais são as entradas do problema? Quais são as saídas? Que variáveis devem ser criadas, e quais devem ser seus valores iniciais? Que etapas intermediárias devem ser realizadas para computar outros valores e para afinal computar a saída? Essas etapas repetem instruções que podem ser escritas de forma simplificada usando um laço?
Vamos ver como descrever cuidadosamente a busca binária. A ideia principal da busca binária é controlar a faixa atual de suposições razoáveis. Vamos dizer que estou pensando em um número entre um e 100, assim como o jogo de adivinhação. Se você já tiver tentado o 25 e eu tiver dito que meu número é maior, e já tiver tentado o 81 e eu tiver dito que meu número é menor, então os números na faixa de 26 a 80 são as únicas suposições razoáveis. Aqui, a seção vermelha da reta numérica contém as suposições razoáveis, e a seção preta as suposições que já foram descartadas:
A cada vez, você faz uma suposição que divide o conjunto de suposições razoáveis em duas faixas de tamanho aproximadamente igual. Se sua suposição não estiver correta, eu lhe direi se ela é alta ou baixa demais, e você vai pode eliminar cerca de metade das suposições razoáveis. Por exemplo, se o intervalo corrente de suposições razoáveis é de 26 a 80, você pode adivinhar o ponto do meio, left parenthesis, 26, plus, 80, right parenthesis, slash, 2, ou 53. Então, se eu digo a você que 53 é muito alto, você pode eliminar todos os números de 53 a 80, deixando 26 a 52 como o novo intervalo de valores razoáveis, reduzindo pela metade o intervalo.
Para o jogo de adivinhação, podemos controlar o conjunto de suposições razoáveis usando algumas variáveis. Vamos deixar a variável m, i, n  ser a suposição razoável miníma desta partida, e a variável m, a, x  será a suposição razoável máxima. A entrada do problema é o número n, o maior número que seu oponente pode estar pensando. Assumimos que o menor valor possível é um, mas isto poderia ser facilmente modificado no algoritmo para pegar valores menores como uma segunda entrada.
Aqui está uma descrição em pseudocódigo da busca binária:
  1. Defina que m, i, n, equals, 1 e m, a, x, equals, n.
  2. Encontre a média de m, a, x e m, i, n, arredondando para baixo para que seja um inteiro.
  3. Se você tiver adivinhado o número certo, pare. Você o encontrou!
  4. Se o palpite foi muito baixo, defina o m, i, n como 1 a mais do que o palpite.
  5. Se o palpite foi muito alto, defina o m, a, x como 1 a menos do que o palpite.
  6. Volte ao passo dois.
Poderíamos fazer esse pseudocódigo ainda mais preciso descrevendo claramente as entradas e as saídas do algoritmo, além de esclarecer o que queremos dizer com instruções como "adivinhe um número" e "pare". Mas isso é o bastante por enquanto.

Este conteúdo é uma colaboração entre os professores Thomas Cormen e Devin Balkcom da Dartmouth Computer Science e a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.