Implementação de busca binária de um array

Vamos ver como pensar na busca binária em um array organizado. Sim, o JavaScript proporciona métodos para determinar se um dado elemento está em um array e, se estiver, sua posição (assim como muitas linguagens de programação), mas queremos implementar isso nós mesmos, para entender como implementar métodos desse tipo. Aqui está um array JavaScript dos 25 primeiros números primos, em ordem:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Suponha que desejemos saber se o número 67 é primo. Se 67 estiver no array, então ele é primo.
Podemos também querer saber quantos números primos são menores que 67. Se descobrirmos a posição do número 67 no array, podemos usar essa informação para descobrir quantos números primos menores que ele existem.
A posição de um elemento em um array é conhecida como seu índice. Os índices dos arrays começam em 0 e são contados de forma crescente. Se um elemento estiver no índice 0, ele é o primeiro elemento do array. Se um elemento estiver no índice 3, então ele tem elementos 3 antes dele no array.
Examinando o exemplo abaixo, podemos ler o array de números primos da esquerda para a direita, um por vez, até descobrirmos o número 67 (na caixa rosa) e vermos que ele está no índice 18 do array. Looking through the numbers in order like this is a linear search.
Uma vez que sabemos que o número primo 67 está no índice 18, podemos identificá-lo como um primo. Também podemos identificar rapidamente que há 18 elementos antes do 67 no array, o que significa que há 18 números primos menores que 67.
Você notou quantas etapas foram necessárias? Uma busca binária poderia ser mais eficiente. Como o array primes contém 25 números, os índices do array variam entre 0 e 24. Usando nosso pseudocódigo anterior, começamos fazendo min = 0 e max = 24. A primeira suposição na busca binária estaria, então no índice 12 (que é igual a (0+24)/2). primes[12] é igual a 67? Não, primes[12] é igual a 41.
Linhas números 26 a 52 da busca binária
O índice que estamos procurando é maior ou menor do que 12? Como os valores no array estão em ordem crescente, e 41 < 67, o valor 67 deve estar à direita do índice 12. Em outras palavras, o índice que estamos tentando encontrar deve ser maior do que 12. Atualizamos o valor de min para 12 + 1, ou 13, e mantemos o max igual a 24.
Linhas números 26 a 52 da busca binária
Qual é a próxima suposição de índice? A média entre 13 e 24 é 18,5, que podemos arredondar para 18, já que os índices dos arrays devem ser números inteiros. Descobrimos que primes[18] é 67.
Linhas números 26 a 52 da busca binária
O algoritmo da busca binária para neste ponto, já que encontrou a resposta. Foram necessárias apenas duas tentativas em vez das 19 tentativas de que a busca linear precisaria. Você pode acompanhar o processo novamente na visualização abaixo:

Pseudocódigo

Acabamos de descrever o algoritmo da busca binária em português, acompanhando um exemplo. Este é um modo de fazer isso, mas uma explicação em linguagem humana pode variar em qualidade. Ela pode ser curta demais ou longa demais, e, mais importante, ela nem sempre é tão precisa quanto deveria. Poderíamos pular isso para mostrar a você uma busca binária em uma linguagem de programação como JavaScript ou Python, mas programas contêm muitos detalhes - devido a requerimentos impostos pela linguagem de programação, ou porque eles devem lidar com erros causados por dados corrompidos, ou falhas do sistema - e isso pode dificultar a compreensão do algoritmo fundamental se estudarmos apenas o código. É por isso que preferimos descrever os algoritmos em algo chamado pseudocódigo, que mistura português com características que se vê em linguagens de programação.
Aqui está um pseudocódigo para a busca binária, modificado para realizar uma busca em um array. As entradas são o array, que chamamos de array; o número n de elementos no array; e o alvo (target), número buscado primeiramente. A saída é o índice do alvo no array.
  1. Defina min = 0 e max = n-1.
  2. Calcule chute como sendo a média entre max e min, arrendonde para baixo (então será um número inteiro).
  3. Se array[chute] for igual ao alvo, então pare. Você o encontrou! Retorne chute.
  4. Se o chute for muito baixo, ou seja, array[chute] < alvo, então defina min = chute + 1.
  5. Caso contrário, o chute foi muito alto. Defina max = chute - 1.
  6. Volte para o passo 2.

Implementação do pseudocódigo

Vamos alternar entre português, pseudocódigo e JavaScript nesses tutoriais, dependendo da situação. Como programador, você deve aprender a entender o pseudocódigo e ser capaz de convertê-lo na sua linguagem escolhida - então, embora estejamos usando JavaScript aqui, deve ser simples para você implementar pseudocódigo em outras linguagens.
Como poderíamos converter esse pseudocódigo em um programa JavaScript? Devemos criar uma função, porque estamos escrevendo um código que aceita uma entrada e retorna uma saída, e queremos que esse código seja reutilizável para diferentes entradas. Os parâmetros da função — vamos chamá-la binarySearch — serão o array e o valor alvo (target), e o valor de retorno da função será o índice da posição onde o valor alvo foi encontrado.
Agora, vamos examinar o corpo principal da função, e decidir como implementá-lo. A etapa 6 diz para voltar para a etapa 2. Isso parece ser um laço. Ele deve ser um laço for ou um laço while? Se você realmente quisesse usar um laço for, poderia fazê-lo, mas os índices supostos pela busca binária não estão na ordem sequencial que o laço for torna-se conveniente. Primeiro, podemos selecionar o índice 12, então o 18, com base em algumas computações. Então, um laço while é a melhor opção.
Há também uma etapa importante faltando nesse pseudocódigo que não era importante no jogo de adivinhação, mas é importante na busca binária de um array. O que deve acontecer se o número que você está procurando não estiver no array? Vamos começar descobrindo qual índice a função binarySearch deve retornar neste caso. O índice deve ser um número que não pode ser válido no array. Vamos usar -1, já que este não pode ser um índice válido em nenhum array. (Na verdade, qualquer número negativo servirá.)
O número alvo não estará no array se não houver mais possíveis chutes. Em nosso exemplo, suponha que estamos procurando pelo alvo número 10 no array primes. Se o 10 estivesse lá, ele estaria entre os números 7 e 11, que estão nos índices 3 e 4. Se você rastrear os índices dos valores para min e max assim como a função binarySearch faz, você descobriria que eles eventualmente estariam no ponto onde min é igual a 3 e max é igual a 4. O chute é então o índice 3 (como (3 + 4) / 2 é igual a 3.5, e arredondamos para baixo), e primes[3] é menor que 10, desta forma, min se torna 4. Com ambos, min e max valendo 4,o chute deve ser o índice 4, e primes[4] é maior que 10. Agora max se torna 3. O que isso significa, min ser igual a 4 e max ser igual a 3? Isso significa que os únicos possíveis chutes são no mínimo 4 e no máximo 3. Não existe esse número no array! Neste ponto, podemos concluir que o alvo 10, não está no array primes, e a função binarySearch retornaria -1. Em geral, uma vez que max se torna estritamente menor que min, nós sabemos que o número alvo não está no array ordenado. A seguir está o pseudocódigo modificado para a busca binária que lida com o caso em que o número alvo não está no array:
  1. Defina min = 0 e max = n-1.
  2. Se max < min, então pare: o alvo não está presente no array. Retorne -1.
  3. Calcule o chute como sendo a média entre max e min, arredondando para baixo (então será um número inteiro).
  4. Se array[chute] for igual ao alvo, então pare. Você o encontrou! Retorne chute.
  5. Se o chute foi muito baixo, ou seja, array[chute] < alvo, então defina min = guess + 1.
  6. Caso contrário, o chute foi muito alto. Defina max = guess - 1.
  7. Volte para o passo 2.
Agora que analisamos o pseudocódigo juntos, você vai tentar implementar a busca binária por conta própria. Tudo bem dar uma olhada no pseudocódigo - de fato, isso é bom, porque assim você vai compreender melhor o que significa converter um pseudocódigo em um programa.

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