Como funciona o algoritmo de busca binária?

A pesquisa binária funciona analisando um array ordenado, dividindo sucessivamente o intervalo de pesquisa ao meio.

1. Inicialização: Define-se a fronteira esquerda e direita do intervalo de pesquisa (geralmente o início e o fim do array).
2. Comparação: Calcula-se o índice do meio do intervalo. O valor nesse índice é comparado com o elemento procurado.
3. Redução do intervalo:
   • Se o valor no meio coincide com o procurado, o elemento foi encontrado.
   • Se o valor no meio for maior que o procurado, a busca continua na metade esquerda do intervalo. A fronteira direita move-se para meio - 1.
   • Se o valor no meio for menor que o procurado, a busca continua na metade direita do intervalo. A fronteira esquerda move-se para meio + 1.
4. Repetição: Os passos 2 e 3 são repetidos até que o elemento seja encontrado ou o intervalo de pesquisa fique vazio.

A complexidade do algoritmo é O(log n), o que é muito mais eficiente do que a busca linear para arrays grandes.

Exemplo de implementação em Python:

def binary_search(arr, target):
    """
    Implementação de busca binária.
    Recebe um array ordenado e o valor procurado.
    Retorna o índice do elemento ou -1 se não for encontrado.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calcula o índice do meio
        mid_val = arr[mid]      # Obtém o valor no meio

        if mid_val == target:
            return mid  # Elemento encontrado
        elif mid_val < target:
            left = mid + 1  # Valor procurado é maior, busca na direita
        else: # mid_val > target
            right = mid - 1 # Valor procurado é menor, busca na esquerda

    return -1 # Elemento não encontrado