Pesquisa binária em Python – Como escrever o algoritmo de pesquisa binária e exemplos

Artigo original: https://www.freecodecamp.org/news/binary-search-in-python-with-examples/

Diariamente, estamos procurando por informações ou tentando encontrar soluções para os problemas que encontramos.

Ao percorrer os resultados de uma pesquisa na web, escolhemos os artigos ou recursos mais relevantes que acreditamos que nos ajudarão a encontrar a resposta.

Pesquisar faz parte de nossas vidas, pois nem sempre podemos ter as respostas. Do mesmo modo, existem vários algoritmos que ajudam os programas a serem executados de modo mais eficiente e a lidar com os dados de maneira mais eficaz.

O que abordaremos neste tutorial

• O que é um algoritmo de pesquisa?
• O que é um algoritmo de pesquisa binária?
• Como funciona a pesquisa binária – Dividir e conquistar
• Processos envolvidos em algoritmos de pesquisa binária
• Métodos usados ​​em algoritmos de pesquisa binária
• Exemplos reais de pesquisa binária

O que é um algoritmo de pesquisa?

Um algoritmo de pesquisa trabalha para recuperar itens de qualquer estrutura de dados. Ele compara os dados que são inseridos na entrada com as informações armazenadas no banco de dados e traz o resultado. Um exemplo é encontrar o número de telefone do seu melhor amigo na sua lista de contatos com 1.000 números.

Existem diferentes tipos de algoritmos de pesquisa. Vejamos alguns deles:

Algoritmos de pesquisa linear

Os algoritmos de pesquisa linear são os mais simples de todos os algoritmos de pesquisa. Como o nome indica, eles operam em uma sequência (de modo linear).

A pesquisa linear verifica os elementos em uma lista, um após o outro, para localizar o item que corresponda ao valor específico. Quando encontra um item que corresponda à procura, o algoritmo retorna a posição desse item.

Algoritmo de Dijkstra

O algoritmo do caminho mais curto de Dijkstra é mais usado em pesquisas avançadas. O algoritmo de Dijkstra mapeia a distância mais curta entre dois nós. Esses nós geralmente são rotas de redes.

Esse tipo de pesquisa é útil quando você está tentando encontrar rotas em mapas. Ele oferece opções baseadas em encontrar o caminho mais curto possível.

Algoritmo de pesquisa binária

Os algoritmos de pesquisa (ou de busca) binária também são conhecidos como pesquisa de meio intervalo. Eles retornam a posição do valor pesquisado em uma lista classificada.

Esses algoritmos usam a técnica de "dividir e conquistar" para encontrar a posição do valor.

Tanto os algoritmos de pesquisa binária quanto os de pesquisa linear são exemplos de algoritmos de pesquisa simples.

Na pesquisa binária, o elemento que fica no meio da lista é encontrado antes de ser feita a comparação com o valor do item que você está procurando. Na pesquisa linear, os elementos são obtidos um a um na lista, percorrendo e comparando com o valor da chave.

‌Na pesquisa binária, a lista é dividida em duas partes para obter o elemento do meio: temos os itens à esquerda, o elemento do meio e os itens à direita.

Os itens da esquerda contém valores menores que o elemento do meio enquanto os da direita têm valores maiores que ele. Esse método precisa de uma lista ordenada para funcionar.

Uma lista ordenada tem seus itens organizados em uma ordem específica. Geralmente, eles estão em ordem crescente, onde o valor de um item deve ser sempre maior que o anterior. Para tornar a pesquisa binária eficiente, os valores da lista devem ser organizados corretamente nessa ordem para satisfazer o processo da pesquisa. Se uma lista tiver seus valores desorganizados, ela deve ser ordenada por um algoritmo de classificação antes da realização da pesquisa.

Algoritmos de ordenação

Os algoritmos de ordenação aceitam uma lista não classificada como entrada e retornam uma lista com os elementos organizados em uma ordem específica (principalmente na ordem crescente).

Existem diferentes tipos de algoritmos de ordenação, como ordenação por inserção, ordenação rápida, ordenação por bolha e ordenação por mesclagem.

Como funciona a pesquisa binária – dividir e conquistar

Um algoritmo de busca binária usa uma técnica chamada "dividir e conquistar" para resolver sua tarefa. O algoritmo de ordenação por mesclagem emprega a mesma técnica para classificar itens em uma lista.

Em algoritmos de pesquisa binária, o método "dividir e conquistar" funciona deste modo:

• Divide a lista em duas partes: o lado esquerdo e o lado direito, separados pelo item do meio
• Cria uma variável para armazenar o valor do item procurado
• Seleciona o elemento do meio e o compara com o item procurado
• Se os itens comparados forem iguais, retorna a posição do elemento do meio e o processo termina
• Caso contrário, o elemento do meio será maior ou menor que o item que você está procurando. Se for maior, o algoritmo pega a lista da esquerda e recomeça a divisão do primeiro passo, até achar o elemento ou percorrer toda a lista. Se o elemento do meio for menor, ele pega a lista da direita e recomeça o processo.

Você pode implementar esse método usando recursão ou iteração no processo de pesquisa binária.

Como funciona o algoritmo de pesquisa binária – passo a passo

Primeiro, antes de realizar a pesquisa, você precisa classificar a lista.

Em seguida, você cria uma variável que armazena o valor a ser pesquisado.

A seguir, a lista é dividida em duas partes. Somamos o primeiro e o último índices, e dividimos por dois para encontrar o índice do elemento do meio na lista.

Quando o valor resultante do cálculo é um float (como 3,45), assumimos a parte inteira como o índice do elemento do meio.

Em seguida, comparamos o valor que estamos procurando e o elemento do meio.

Caso de uso da pesquisa binária

Condição 1

Se o elemento do meio for igual ao valor a ser pesquisado, a posição em que o valor está será retornada e o processo é finalizado.

if elemento_do_meio == valor_pesquisado 
    return posição_do_elemento_do_meio
*fim do código* 

Usando a imagem acima como exemplo:

O elemento do meio é igual a 23 e valor_pesquisado é igual a 23. Comparando os dois valores, vemos que eles são iguais. Como o elemento do meio aparece no índice 2 na lista, este é o valor de retorno do código. O processo termina.

Condição 2

Se o elemento do meio não for igual a "valor_pesquisado", verificamos os seguintes cenários:

Cenário 1: se o elemento do meio for maior que o valor pesquisado:

if elemento_do_meio > valor_pesquisado

• a pesquisa passa para o lado esquerdo porque os valores são menores que o elemento do meio
• a variável nova_posicao muda para a anterior ao índice do elemento do meio
• nova_posicao = indice(elemento_do_meio) - 1
• uma nova pesquisa começa, mas agora só procura nos valores anteriores ao índice da nova posição.

Usando a imagem acima como exemplo:

elemento_do_meio = 23
valor_pesquisado = 4
if 23 > 4 

• passamos para o lado esquerdo, pois todos os números menores que 23 estão armazenados à esquerda. O índice(de 23) é 2
• nova_posicao = indice(23) - 1 = 2 - 1 = 1
• A pesquisa terminará no índice 1 e pegará todos os valores antes do índice 1

Comparando o valor do novo elemento do meio (4) com o valor pesquisado (4), vemos que são iguais. Assim, a pesquisa é encerrada e o retorno é a posição que "4" ocupa na lista (que é o índice 0).

Cenário 2: se o elemento do meio for menor que o valor a ser pesquisado:

if elemento_do_meio < valor_pesquisado

• a pesquisa passa para o lado direito porque os valores são maiores que o elemento do meio
• a variável nova_posicao muda para a posterior ao índice do elemento do meio
• nova_posicao = indice(elemento_do_meio) + 1
• uma nova pesquisa começa com o intervalo de pesquisa entre a nova posição e o último índice da lista

Usando a primeira imagem como exemplo:

elemento_do_meio = 23 
valor_pesquisado = 32 
if 23 > 32 

• passamos para o lado direito porque todos os números maiores que 23 estão à direita: índice(23) = 2 ,
• nova_posicao = indice(23) + 1 = 2 + 1 = 3
• Uma nova pesquisa começará com todos os valores após o índice 3

Comparando o elemento do meio (32) com o valor pesquisado (32), vemos que eles são iguais. Assim, a pesquisa é encerrada e o retorno é a posição que "32" ocupa na lista (índice 4).

‌‌Métodos usados ​​em algoritmos de pesquisa binária

Existem dois métodos que podem implementar a técnica "dividir e conquistar" na pesquisa. Eles são a iteração e a recursão.

O que é Iteração?

Para obter elementos de uma tupla, lista ou um dicionário, você itera pelos itens com laços.

A iteração é a repetição de uma sequência de instruções durante a execução e possui um número contável de valores. Por exemplo, ao percorrer listas aleatórias, percorremos a variável real que contém as listas para obter esses valores.

Implementação em código da pesquisa binária com iteração

Este é o código:

def pesquisa_binaria(lista_de_numeros , valor_pesquisado):
    primeiro_indice = 0
    tamanho = len(lista_de_numeros)
    ultimo_indice = tamanho - 1
    indice_elemento_do_meio = (primeiro_indice + ultimo_indice) // 2
    elemento_do_meio = lista_de_numeros[indice_elemento_do_meio]

    encontrado = True
    while encontrado:
        if primeiro_indice == ultimo_indice:
            if elemento_do_meio != valor_pesquisado:
                encontrado = False
                return "Não aparece na lista"

        elif elemento_do_meio == valor_pesquisado:
            return f"{elemento_do_meio} encontrado na posição {indice_elemento_do_meio}"

        elif elemento_do_meio > valor_pesquisado:
            nova_posicao = indice_elemento_do_meio - 1
            ultimo_indice = nova_posicao
            indice_elemento_do_meio = (primeiro_indice + ultimo_indice) // 2
            elemento_do_meio = lista_de_numeros[indice_elemento_do_meio]
            if elemento_do_meio == valor_pesquisado:
                return f"{elemento_do_meio} encontrado na posição {indice_elemento_do_meio}"

        elif elemento_do_meio < valor_pesquisado:
            nova_posicao = indice_elemento_do_meio + 1
            primeiro_indice = nova_posicao
            ultimo_indice = tamanho - 1
            indice_elemento_do_meio = (primeiro_indice + ultimo_indice) // 2
            elemento_do_meio = lista_de_numeros[indice_elemento_do_meio]
            if elemento_do_meio == valor_pesquisado:
                return f"{elemento_do_meio} encontrado na posição {indice_elemento_do_meio}"



lista = [16 , 18 , 20 , 50 , 60 , 81 , 84 , 89]
print(pesquisa_binaria(lista , 81))
print(pesquisa_binaria(lista , 10))

Agora, vamos ver o que está acontecendo nele:

• Primeiro, passamos uma lista e um valor a ser pesquisado (valor_pesquisado) como parâmetros (entrada) para uma função.
• Na função, criamos uma variável primeiro_indice para o primeiro índice da lista pesquisada e o atribuímos a "0". O primeiro índice de uma lista é sempre "0".
• Em seguida, criamos quatro variáveis: tamanho para armazenar o tamanho da lista, ultimo_indice para armazenar o índice do último elemento da lista,  indice_elemento_do_meio  para armazenar o resultado da operação que encontra o índice do elemento do meio e elemento_do_meio para armazenar o valor do elemento do meio, obtido da lista, usando-o como posição.
• Depois, introduzimos um laço while para fazer com que as condições sejam executadas repetidamente. Acima do laço while criamos uma variável chamada encontrado e a definimos como "True". Essa condição verifica se o "item a ser pesquisado" foi encontrado ou não.
• No laço while, verificamos todas as condições. A primeira condição é verificar se o elemento do meio e a variável valor_pesquisado são iguais. Se forem iguais, a posição do item será retornada.
• Em seguida, verificamos a segunda condição, que é se elemento_do_meio != valor_pesquisado (!= verifica se é diferente), que nos leva aos dois cenários:
  – se o elemento do meio for maior que o item a ser pesquisado, a variável nova_posicao é definida como o índice anterior ao índice do elemento do meio (pois já sabemos que o elemento do meio não é o que procuramos). A pesquisa continuará. começando no primeiro índice, mas agora terminará na nova posição, cujo valor, agora é atribuído à variável ultimo_indice.
  – Se o elemento do meio for menor que o item a ser pesquisado, a variável nova_posicao será definida com o índice posterior ao índice do elemento do meio. A variável primeiro_indice recebe esse valor dela, fazendo com que o intervalo de pesquisa agora comece a partir dessa nova posição e termine no último índice.

Ao final desses cenários, verificamos se o novo elemento do meio é o mesmo que o item pesquisado. Se for o mesmo, a posição do item será retornada. Caso contrário, as condições serão verificadas até que os valores sejam iguais.

É possível, no entanto, que aconteçam erros, por exemplo, em que o valor que estamos procurando não aparece na lista. Se terminarmos o código só com essas duas condições, o laço continuará executando e eventualmente travará o sistema.

A fim de detectarmos esse erro, definimos uma condição para verificar se o primeiro índice é igual ao último índice. Em seguida, verificamos se o elemento do meio é igual ao item pesquisado. Se não for igual, a variável encontrado será definida como False e retornará a frase "Não aparece na lista", já que no código, o retorno é sempre uma frase.

A etapa final é chamar a função e o resultado a ser exibido.

Aqui estão os resultados:

Se o elemento estiver na lista, o retorno será a posição.

Se o elemento não estiver na lista, o retorno será uma frase como esta:

O que é ‌‌recursão?

Uma função é dita recursiva se faz referência a si mesma ou a termos anteriores para resolver uma tarefa.

Uma função recursiva é repetitiva e é executada em sequência. Ela começa a partir de um problema complexo e o divide em problemas mais simples.

Implementação em código da pesquisa binária usando recursão

Com recursão, fica um pouco mais simples e requer menos código. O código terá essa aparência:

def pesquisa_binaria(lista_de_numeros, primeiro_indice, ultimo_indice, valor_pesquisado):
    if ultimo_indice >= primeiro_indice:
       
        indice_elemento_do_meio = (primeiro_indice + ultimo_indice) // 2
        elemento_do_meio = lista_de_numeros[indice_elemento_do_meio]
       
 
        if elemento_do_meio == valor_pesquisado:
            return f"{elemento_do_meio} encontrado na posição {indice_elemento_do_meio}"
 
        elif elemento_do_meio > valor_pesquisado:
            nova_posicao = indice_elemento_do_meio - 1
            # novo último índice é a nova posição
            return pesquisa_binaria(lista_de_numeros, primeiro_indice, nova_posicao, valor_pesquisado)
 
        elif elemento_do_meio < valor_pesquisado:
            nova_posicao = indice_elemento_do_meio + 1
             #novo primeiro índice é a nova posição
            return pesquisa_binaria(lista_de_numeros, nova_posicao, ultimo_indice, valor_pesquisado)
 
    else:
        return "Não aparece na lista"
       
lista = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
pesquisar = 34
primeiro = 0
ultimo= len(lista) - 1
 
print(pesquisa_binaria(lista,primeiro,ultimo,pesquisar))

• Primeiro, a função aceita quatro argumentos:  primeiro_indice, ultimo_indice, lista_de_numeros e valor_pesquisado.
• Em seguida, verificamos se o valor do último índice é maior ou igual ao valor do primeiro índice. Se a condição for verdadeira, atribuímos a operação de encontrar o índice do elemento do meio à variável chamada  indice_elemento_do_meio. Então, o valor de elemento_do_meio é obtido da lista usando o indice_elemento_do_meio como posição.
• Criamos uma instrução "if" sob o primeiro bloco "if" para verificar se o elemento do meio e a variável valor_pesquisado são iguais. Se forem iguais, a posição do item será retornada.
• Em seguida, verificamos a segunda condição, que é se elemento_do_meio != valor_pesquisado, o que nos leva a dois cenários:
  – se o elemento do meio for maior que o item pesquisado, a variável nova_posicao será o índice anterior ao elemento do meio. Agora, retornamos a própria função e passamos o valor de nova_posicao no parâmetro do ultimo_indice.
  – se o elemento do meio for menor que o item pesquisado, nova_posicao será o índice posterior ao elemento do meio. Retornamos a própria função com o valor de nova_posicao substituindo o parâmetro primeiro_indice.
• A última condição estará no mesmo encadeamento da primeira instrução "if". Se o valor_pesquisado não estiver na lista, ele retornará a frase "Não está na lista".

A etapa final é chamar a função e exibir o resultado.

Aqui estão os resultados:

Se o elemento estiver na lista, retornará sua posição:

Se o elemento não estiver na lista, retornará uma frase:

Exemplos reais de pesquisa binária‌

Você pode não perceber, mas realizamos pesquisas binárias o tempo todo. Aqui estão alguns exemplos de como você pode encontrá-la no seu dia-a-dia ou no trabalho:

• Procurando uma palavra em um dicionário
• Procurando um livro de literatura na seção de literatura em uma biblioteca
• Procurando um elemento em uma lista ordenada
• Procurando alunos com mais de 1,50 m de altura em uma fila de alunos organizados de acordo com suas alturas.

Conclusão

Agora, você deve estar familiarizado com o funcionamento dos algoritmos de pesquisa binária e com sua implementação em código.

Não é um problema se você não conseguir entender tudo de uma vez – apenas dê a si mesmo um tempo e vá praticando os algoritmos. Se encontrar algum erro ou se tiver dúvidas, entre em contato com a autora pelo Twitter.

‌‌