2 min read

O algoritmo de busca bin√°ria (Binary Search)

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