Binary Search for Dummies[Sem Ofensa]

Recentemente aprendi sobre pesquisa binária(binary search) ao terminar o capítulo do livro "Entendendo Algoritmos"(super recomendo). Decidi ser útil para a comunidade, e ensinar de um jeito simples como implementar ess

Frase motivacional: "Nada é difícil, aprenda do jeito mais divertido possível e divirta-se."😉

O que é pesquisa?

Tá, foi mal por te fazer pensar até ai, mas é importante saber. Pesquisar significa procurar informação sobre um assunto, ou investigar algum fenômeno ou evento. Contextualizado, pesquisar é procurar um item/elemento em uma sequência de valores.

Existem dois tipos de pesquisa: pesquisa simples e a pesquisa binária. Vamos começar por entender a mais simples, que é justamente...

Pesquisa Simples

Um algoritmo de pesquisa simples, passa por todos os que antecedem o elemento que queremos encontrar, então vc concorda comigo que no pior dos casos eu teria que passar por toda a sequência para um valor, no caso o último?

Vamos ver um exemplo:

numbers: list = [1, 2, 3, 4, 5, 6] # uma sequência
def seq_search(seq: list, target: int) -> str:
    """
    seq_search: uma função que faz um pesquisa simples
    sobre uma sequência para encontar um valor.
    params: 
        seq: list -> sequência de valores
        target: int -> valor que queremos encontrar
    """
    for index, number in enumerate(seq): # vamos iterar por toda a sequência com o método    enumerate que permite obter o index do valor 
        if number == target: # se o valor actual for igual ao target
            return f"O valor {target} está no index(posição) {index}." 
         return "Valor não encontrado!"
seq_search_result = seq_search(numbers, 4)
print(seq_search_result)
\# Saída: "O valor 4 está no index(posição) 3."

Calma aí, o valor 4 não deveria estar no index(posição) 3? Não, em programação a indexação dos elementos num sequência começa por 0, não por 1.

Veja no exemplo abaixo:

Para quem prefere uma abordagem com animação: Clique Aqui

Já uma ...

Binary search(Pesquisa Binária)

É um algoritmos que fornece uma forma mais rápida de encontrar itens numa sequência ordenada de valores.

Esse algoritmo requer duas entradas uma sequência ordenada de valores, e o valor que você pretende encontrar. Ele funciona da seguinte forma: temos dois ponteiros, um aponta para o index 0(a posição do primeiro valor), e ou outra para o último index, ou seja len(numbers) - 1, a última posição na sequência.

A seguir, precisamos a partir desses dois ponteiros encontrar o elemento no meio da sequência uma forma de calcular isso é usando a seguinte fórmula:

Onde: left: é uma variável que conterá o index do primeiro elemento da sequência, ou seja, 0.
right: esta por sua vez, conterá o index do último elemento da sequência, ou seja, len(seq) - 1
Deve estar a perguntar-se por quê utilize // ao invés de /, numa sequência os indexes jão identificados por números inteiros, por isso precisamos utilizar //, pois realizaremos uma divisão inteira que retorna apenas a parte inteira da divisão, exemplo: 5 / 2 = 2.5, e 5 // 2.

Veja a imagem abaixo:

Partiu implementar isso:

numbers = [1, 2, 3, 4, 5, 6] # uma sequência ordenada de valores

def binary_search(seq: list, target: int) -> int | str:
    """
    binary_search: pesquisa por um valor numa sequência ordenada de valores.
    params: 
        seq: list -> sequência ordenada de valores
        target: int -> valor a encontrar
    """
    left = 0 # ponteiro para o index do primeiro elemento
    right = len(seq) - 1 # ponteiro para o index do último elemento
    
    while left <= right: # enquanto o ponteiro da esquerda for menor ou igual a da direita, faça...

        middle = (left + right) // 2 # ache o index do elemento no meio da sequência
        
        if seq[middle] == target: # se o valor no meio da sequência for igual ao target
            return middle # retorne a posição do elemento
        elif target < seq[middle]: # se o meu target for menor que o valor no meio da sequência então eu mudo a posição do meu ponteiro right, pois o target pode estar antes do middle
            right = middle - 1 
        else: # se não, quer dizer que o target é maior que o valor no meio da sequência por isso mova o left para o valor depois do middle, pq o middle eu já sei que não, verifiquei acima. (if seq[middle] == target)
            left = middle + 1
    return "Valor não encontrado" # se ele fizer todas as iterações e não encontrar retorne isso
    
binary_search_result = binary_search(numbers, 4)
print(binary_search_result)
\# Saída: 3

Não entendeu, calme acontece, kkk.

Tente visualizar nesse site, pode ajudar.

Concluindo, utilize a pesquisa simples para sequências pequenas e desordenadas, as pesquisa binária para pesquisas mais eficientes em sequências ordenadas(desordenadas também é só ordenar antes, kkk)

É isso, muito obrigado por ler. Deixe dicas e sugestões nos comentários.