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:

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. Olhar para os números na ordem é uma busca linear.

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ê viu quantos movimentos foram necessários? Uma busca binária pode ser mais eficiente. Como o array primes contém 25 números, os índices no array variam de 0 até 24. Com base nas instruções do passo a passo do artigo anterior, começamos definindo min = 0 e max = 24. O primeiro palpite na busca binária seria, portanto, no índice 12 (que é (0 + 24) / 2). O primes[12] é igual a 67? Não, primes[12] é 41.

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.

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.

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:

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.

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 em algum momento eles 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:

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.