O algoritmo de busca binária (Binary Search)

Introdução

A busca binária ou pesquisa binária é um algoritmo que possui o conceito "divisão e conquista", tendo como premissa um vetor ordenado, onde serão realizadas divisões ao meio do vetor, reduzindo a análise por amostras do vetor a cada iteração. Diferentemente da busca linear onde podemos ter um custo de percorrer todo o vetor.

Implementação

A implementação do algoritmo foi feita em Python, uma linguagem que eu considero adequada para estudos de algoritmos.

def binary_search(numbers, search):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2

        # ensure the element is in the middle.
        if search is numbers[middle]:
            return middle

        # increase left cursor when middle is less (lt) than search.
        elif numbers[middle] < search:
            left = middle + 1
        # when the middle is greater than search, the right cursor will be reduced.
        else:
            right = middle - 1

    return -1

Esta implementação trabalha com três cursores esquerda (left), meio (middle) e direita (right), a cada iteração validamos se o valor do meio é o alvo, caso contrário os cursores left e right serão ajustados e no inicio do loop (while) ocorre o calculo do meio do vetor, considerando uma nova amostra de vetor.

1. No caminho feliz encontramos o alvo no meio do vetor;
2. Caso contrário, o cursor esquerdo será ajustado (meio +1) quando o valor da extremidade esquerda for menor que o alvo;
3. Caso contrário o cursor da direta será ajustado (meio -1) caso a condição anterior não seja atendida;

As instruções abaixo definem um teste usando pytest para validar a implementação do algoritmo.

Você pode manter a função e o teste em um único arquivo.

def test_binary_search():
    numbers = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    index = binary_search(numbers, 34)
    assert index == 9

Para executar digite pytest e nome do arquivo, exemplo:

pytest binary_search.py

Teste de mesa

Para entender a lógica do algoritmo temos o teste de mesa com cada iteração, lembrando que o número escolhido foi o 21.

Fim!

Espero que a abordagem tenha ajudado a entender ou relembrar esse algoritmo que juntamente ao BubbleSort são temas recorrentes das aulas de algoritmos na faculdade ou cursos.

Mantenha sempre seu kernel atualizado meu amigo!

Referências

• Pesquisa Binária
• Busca linear
• Divisão e Conquista