Pesquisa binária em Python: Um guia completo para uma pesquisa eficiente

Em termos gerais, um algoritmo é uma sequência precisa de instruções que um computador segue para realizar uma tarefa específica ou resolver um problema. Confira nossa publicação no blog, What is an Algorithm (O que é um algoritmo), para saber mais sobre os diversos tipos de algoritmos em machine learning.

Visão geral do conceito

A pesquisa binária é um algoritmo poderoso projetado para encontrar com eficiência um valor em um conjunto de dados ordenado. A ideia central da pesquisa binária é simples: Em vez de verificar cada elemento do conjunto de dados um a um, como em uma pesquisa linear, a pesquisa binária reduz o intervalo de pesquisa pela metade a cada etapa, tornando o processo muito mais rápido.

Veja como funciona:

1. Comece comparando o valor-alvo com o elemento intermediário do conjunto de dados. O índice para o valor médio é calculado usando a fórmula: middle = (low + high) / 2, em que baixo é o índice do primeiro elemento no intervalo de pesquisa atual e alto é o índice do último elemento.
2. Compare o valor médio com o alvo. Se o valor de destino for igual ao elemento do meio, você encontrou o índice e a pesquisa está concluída. Se o valor-alvo for menor que o elemento do meio, a pesquisa continuará na metade esquerda do conjunto de dados. Se o valor-alvo for maior, a pesquisa continuará na metade direita do conjunto de dados.
3. Repita as etapas 1 e 2. O intervalo de pesquisa é continuamente reduzido à metade a cada etapa. Repita o processo até que o valor-alvo seja encontrado ou o intervalo de pesquisa fique vazio.

O processo de pesquisa binária. Imagem do autor

Acima está um exemplo simplificado que demonstra o conceito por trás da pesquisa binária.

Esse processo de redução pela metade é o que torna a pesquisa binária tão eficiente. No entanto, é importante observar que o conjunto de dados deve ser classificado para que a pesquisa binária funcione corretamente. Se os dados não forem classificados, o algoritmo não funcionará como esperado. 

Consulte Data Structures (Estruturas de dados): A Comprehensive Guide With Python Examples para saber mais sobre os diferentes tipos de estruturas de dados que você pode querer pesquisar.

Pontos-chave que você deve lembrar

Os pontos a seguir destacam os princípios fundamentais da pesquisa binária.

Eficiência

A pesquisa binária é significativamente mais rápida do que a pesquisa linear, principalmente quando você lida com grandes conjuntos de dados. Embora a pesquisa linear tenha uma complexidade de tempo de O(n), o que significa que, na pior das hipóteses, ela pode ter que verificar cada elemento, a pesquisa binária é mais eficiente. Ele tem uma complexidade de tempo de O(log n), o que significa que o espaço de pesquisa é reduzido à metade a cada etapa, reduzindo significativamente o número de comparações necessárias.

Para obter uma análise detalhada de como os algoritmos são avaliados, consulte nosso Guia de notação Big O e complexidade de tempo: Intuição e matemática. Uma opção é nosso tutorial Analisando a complexidade do código por meio do Python.

Requisitos

Para que a pesquisa binária funcione, o conjunto de dados deve ser classificado em ordem crescente ou decrescente. Isso é um requisito porque o algoritmo depende da ordem dos elementos para determinar qual metade do conjunto de dados você deve pesquisar em seguida. Se os dados não estiverem classificados, a pesquisa binária não poderá localizar com precisão o valor-alvo.

Flexibilidade

A pesquisa binária pode ser implementada usando uma abordagem iterativa ou recursiva. O método iterativo usa loops para reduzir repetidamente o intervalo de pesquisa pela metade. O método recursivo envolve a função que chama a si mesma com um intervalo de pesquisa menor. Essa flexibilidade se presta bem a diferentes aplicações.

Aplicativos do mundo real

A pesquisa binária é uma ferramenta poderosa. Sua eficiência em restringir rapidamente os intervalos de pesquisa o torna inestimável, principalmente ao lidar com grandes conjuntos de dados em que o desempenho e a velocidade são essenciais. Vamos explorar alguns aplicativos específicos e ver como a pesquisa binária se compara a outros algoritmos.

Bancos de dados

Em bancos de dados, a pesquisa binária é frequentemente usada para localizar rapidamente registros em campos classificados, como encontrar um usuário específico em um banco de dados classificado por ID de usuário. Imagine um banco de dados com milhões de registros. Uma pesquisa linear exigiria a varredura de cada registro um a um, o que poderia levar um tempo considerável. Em vez disso, a pesquisa binária pode identificar rapidamente o registro desejado ao reduzir sistematicamente o espaço de pesquisa pela metade, reduzindo significativamente o número de comparações necessárias.

Ciência de dados

A pesquisa em conjuntos de dados grandes e classificados é uma tarefa comum na ciência de dados. Por exemplo, na análise de séries temporais, a pesquisa binária pode ser usada para localizar registros de data e hora específicos em uma sequência ordenada de eventos. No machine learning, os algoritmos de pesquisa binária podem ser usados para otimizar os hiperparâmetros, encontrando o melhor valor dentro de um intervalo.

Computação gráfica

Na computação gráfica, a pesquisa binária é usada em algoritmos em que a precisão e a velocidade são necessárias. Um exemplo é o ray tracing, uma técnica de renderização usada para simular como a luz interage com os objetos. A pesquisa binária pode ser usada para encontrar rapidamente pontos de interseção entre raios e superfícies.

Blocos de construção para algoritmos complexos

A pesquisa binária não é útil apenas por si só; ela também serve como um bloco de construção para algoritmos e estruturas de dados mais complexos. Por exemplo, as árvores de pesquisa, como as árvores de pesquisa binárias (BSTs), e as árvores balanceadas, como as árvores AVL, baseiam-se nos princípios da pesquisa binária. Essas estruturas permitem operações eficientes de pesquisa, inserção e exclusão, o que as torna úteis quando os dados precisam ser atualizados dinamicamente e pesquisados com frequência. Saiba mais sobre essas árvores em AVL Tree: Guia completo com implementação em Python.

Pesquisa binária versus pesquisa de dados. Outros algoritmos de pesquisa

Vamos explorar como a pesquisa binária se compara a dois outros algoritmos de pesquisa comuns: pesquisa linear e pesquisa de hash.

Pesquisa linear

A pesquisa linear é um algoritmo simples que examina cada elemento em um conjunto de dados sequencialmente. É significativamente menos eficiente do que a pesquisa binária, com uma complexidade de tempo de O(n). No entanto, a pesquisa linear não exige que os dados sejam classificados, o que a torna útil em alguns cenários.

Pesquisa de hash

A pesquisa de hash é um algoritmo eficiente usado para encontrar rapidamente valores em um conjunto de dados quando esses valores estão associados a chaves exclusivas. Ele funciona aplicando uma função de hash à chave, que calcula um índice onde o valor correspondente é armazenado em uma tabela de hash. Isso permite a recuperação quase instantânea de valores, geralmente em tempo O(1). No entanto, embora a pesquisa de hash seja muito rápida para encontrar elementos específicos, ela requer memória adicional para armazenar a tabela de hash e não é adequada para pesquisar em um intervalo de valores, uma tarefa em que a pesquisa binária é mais apropriada.

Implementando a pesquisa binária em Python

Vamos explorar algumas maneiras de implementar uma pesquisa binária simples em Python. Mas, primeiro, precisamos estabelecer um conjunto de dados simples com o qual trabalhar e um valor-alvo a ser pesquisado. Imagine que você tenha a seguinte matriz classificada e um alvo de pesquisa:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56

Método iterativo

O método iterativo talvez seja a abordagem mais direta. Com esse método, usamos um loop while para dividir repetidamente o intervalo de pesquisa pela metade até encontrarmos nosso alvo. Esse método é geralmente preferido por sua clareza e eficiência.

Veja como você pode implementar a pesquisa binária de forma iterativa:

def binary_search_iterative(arr, target):
    # Define the search bounds
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculate the middle index
        mid = left + (right - left) // 2  
        # If the middle element is the target, return its index
        if arr[mid] == target:
            return mid  
        # If the target is bigger, narrow the search to the right half
        elif arr[mid] < target: 
            left = mid + 1  
        # If the target is smaller, narrow the search to the left half
        else: 
            right = mid - 1  
    # Return -1 if the target is not found
    return -1 
    
# Run the iterative function
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Vamos dar uma olhada mais de perto nesse código:

• Começamos definindo "esquerda" e "direita" como os limites do espaço de pesquisa. Inicialmente, left é 0 (o início da matriz) e 'right' é len(arr) - 1 (o final da matriz).

• Em cada iteração, calculamos o índice médio, que representa o meio do intervalo de pesquisa atual. Isso é feito usando a fórmula mid = left + (right - left) /2.

• Em seguida, comparamos o elemento em mid com target:

• Se corresponderem, encontramos nosso alvo e a função retorna mid.

• Se o elemento em mid for menor que o alvo, isso significa que o alvo deve estar na metade direita, então ajustamos left para mid + 1.

• Se o elemento em mid for maior que o alvo, o alvo deverá estar na metade esquerda, portanto, ajustamos right para mid - 1.

• O loop continua até que o alvo seja encontrado ou até que left exceda right, o que significa que o alvo não está na matriz.

Método recursivo

O método recursivo de pesquisa binária é outra maneira de implementar esse algoritmo. Em vez de usar um loop, a função chama a si mesma, ajustando os limites de pesquisa a cada vez até encontrar o alvo ou determinar que o alvo não está presente.

Veja como você pode implementar a pesquisa binária de forma recursiva:

def binary_search_recursive(arr, target, left, right):
    # If the search bounds cross, the target isn't in the array
    if left > right:  
        return -1
    # Calculate the middle index
    mid = left + (right - left) // 2 
    # If middle value equals the target, return the index
    if arr[mid] == target: 
        return mid  
    # If the target is bigger than the middle value, search in the right half
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # If the target is smaller than the middle value, search in the left half
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Run the recursive function
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Vamos dar uma olhada mais de perto nesse código:

• A função recursiva começa com os mesmos limites left e right iniciais que a função iterativa.

• Primeiro, ele verifica se left excede right. Em caso afirmativo, a função retorna -1, indicando que o alvo não está na matriz.

• Caso contrário, a função calcula o índice mid e compara o alvo com o elemento em mid.

• Se o alvo for igual ao elemento em mid, a função retornará mid.

• Se o alvo for maior que mid, a função se chamará recursivamente com limites atualizados para pesquisar a metade direita.

• Se o alvo for menor que mid, a função pesquisará a metade esquerda.

• A recursão continua até que você encontre o alvo ou esgote o espaço de pesquisa.

Para saber mais sobre funções recursivas, consulte Understanding Recursive Functions in Python (Entendendo funções recursivas em Python).

Usando o módulo bisect incorporado do Python

A biblioteca padrão do Python inclui o módulo bisect, que fornece funções de pesquisa binária pré-implementadas. Esse módulo é altamente eficiente e muitas vezes pode nos poupar tempo em vez de criar nossa própria função.

Veja como podemos usar o módulo bisect para localizar o alvo em nossa matriz:

# Import the bisect module
import bisect 

# Call the module and provide the array and the target value
index = bisect.bisect_left(arr, target) 

#Print results
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")

Vamos dar uma olhada mais de perto nesse código:

• A função bisect_left retorna o índice em que o destino deve ser inserido para manter a ordem da matriz. Se o alvo for encontrado nesse índice, isso significa que ele existe na matriz.

• Esse método é particularmente útil quando você trabalha com matrizes ordenadas e também pode ser usado para inserir elementos mantendo a ordem ordenada.

• O módulo bisect também oferece outras funções, como bisect_right e insort, que podem ser usadas para localizar pontos de inserção ou inserir elementos diretamente.

Complexidade de tempo e espaço

Ao discutir a eficiência de um algoritmo, geralmente usamos a notação Big O, representada como O(x), para descrever como o tempo de execução ou os requisitos de espaço aumentam à medida que o tamanho da entrada aumenta. Para a pesquisa binária, a complexidade de tempo é normalmente O(log n). Isso significa que, à medida que o conjunto de dados cresce, o número de operações necessárias para encontrar o alvo aumenta logaritmicamente, tornando a pesquisa binária eficiente mesmo para grandes conjuntos de dados.

O método iterativo de pesquisa binária tem uma complexidade de tempo de O(log n) porque o intervalo de pesquisa é reduzido à metade a cada iteração. Sua complexidade de espaço é O(1), pois usa uma quantidade constante de espaço extra, exigindo apenas algumas variáveis para rastrear os limites de pesquisa e o elemento intermediário.

O método recursivo também tem uma complexidade de tempo de O(log n) pelo mesmo motivo. No entanto, sua complexidade de espaço é O(log n) devido ao espaço necessário para manter a pilha de chamadas para cada chamada recursiva. Como cada chamada recursiva adiciona uma camada à pilha, a profundidade da recursão é proporcional ao número de etapas de redução à metade, que é logarítmico em relação ao tamanho do conjunto de dados.

Embora ambos os métodos sejam eficientes em termos de tempo, a abordagem iterativa é mais eficiente em termos de espaço. É por isso que o módulo bisect usa uma abordagem iterativa sob o capô. Pessoalmente, prefiro a abordagem iterativa também por esse motivo. No entanto, a abordagem recursiva pode ser mais intuitiva para algumas pessoas e pode exigir menos linhas de código.

Armadilhas comuns e como evitá-las

Ao usar uma pesquisa binária, você deve tomar cuidado com algumas armadilhas comuns. Isso pode afetar a correção e a eficiência do seu algoritmo, portanto, é importante que você os observe.

Em primeiro lugar, a pesquisa binária depende do fato de o conjunto de dados estar classificado. Se os dados não estiverem ordenados, a pesquisa binária não funcionará corretamente; ela poderá retornar resultados incorretos ou falhar completamente. Portanto, é essencial classificar nosso conjunto de dados antes de aplicar a pesquisa binária. Se a classificação dos dados não for viável, uma pesquisa binária não é a ferramenta adequada.

Um problema frequente são os erros de um para um. Esses erros ocorrem quando os cálculos de índice estão levemente incorretos, o que pode levar a loops infinitos ou à falha na localização do valor de destino. Isso pode ocorrer se o cálculo do ponto médio ou os ajustes de limite não forem feitos com precisão. Para evitar isso, certifique-se de que os cálculos do índice intermediário estejam corretos e que os limites sejam atualizados corretamente após cada comparação. Lembre-se de que os valores de índice em Python começam em 0, não em 1.

Outro desafio que deve ser observado se você usar a pesquisa binária de forma recursiva são os problemas de profundidade de recursão. Em Python, há um limite para o número de chamadas recursivas que podem ser feitas, para evitar o uso excessivo de memória. Se o seu conjunto de dados for muito grande, a recursão profunda poderá exceder esse limite, causando um estouro de pilha. Para atenuar isso, considere o uso de uma abordagem iterativa para a pesquisa binária, que não sofre com as limitações de profundidade de recursão. Se a recursão for preferida ou necessária, você poderá aumentar o limite de recursão usando sys.setrecursionlimit(), mas isso deve ser feito com cautela para evitar outros possíveis problemas.

Conclusão

A pesquisa binária é um algoritmo poderoso e eficiente que deve estar no kit de ferramentas de todo desenvolvedor Python. Seja implementado de forma iterativa ou recursiva, ele oferece uma vantagem significativa de desempenho em relação à pesquisa linear, especialmente com grandes conjuntos de dados. Para saber mais, confira o programa de habilidades em programação Python da DataCamp ou o curso interativo Princípios de engenharia de software em Python.