Busca Binária

2.1 Definição de busca binária e seus principais conceitos

Busca binária é um algoritmo de busca de um elemento em um array ordenado, que funciona dividindo o array em metades. Esse algoritmo é significativamente mais eficiente que a busca linear para arrays grandes, já que reduz o número de verificações dividindo o array em duas partes a cada iteração.

Principais conceitos:

• Array ordenado: A busca binária funciona apenas em arrays ordenados.
• Divisão ao meio: O algoritmo compara o elemento buscado com o elemento do meio do array.
• Divisão recursiva ou iterativa: Se o elemento buscado for menor que o do meio, a busca continua na metade esquerda do array, senão, na direita.
• Condição de término: A busca para quando o elemento é encontrado ou o intervalo de busca fica vazio.

Importante! Para busca binária é necessário um array ordenado.

Para o funcionamento correto da busca binária, os dados de entrada devem estar ordenados em ordem crescente. Essa é a principal e única exigência, pois o algoritmo se baseia no fato de que os elementos do array estão ordenados. Isso permite que ele exclua eficientemente metade dos elementos a cada passo da busca.

Exemplo de um array ordenado:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Implementação passo a passo da busca binária

Princípio de funcionamento da busca binária:

1. Inicialização: Definir os limites iniciais da busca (limite esquerdo e direito do array).
2. Escolha do elemento do meio: Encontrar o índice do elemento do meio do array.
3. Comparação: Comparar o elemento do meio com o valor buscado.
4. Atualização dos limites:
   1. Se o elemento do meio for igual ao valor buscado, retornar seu índice.
   2. Se o valor buscado for menor que o elemento do meio, atualizar o limite direito da busca.
   3. Se for maior, atualizar o limite esquerdo.
5. Repetição: Repetir os passos 2-4 até encontrar o elemento ou enquanto o limite esquerdo não ultrapassar o direito.

Algoritmo passo a passo:

1. Inicialização: Definir left como 0 e right como len(arr) - 1.
2. Calcular o elemento do meio: mid = (left + right) // 2
3. Comparar com o elemento alvo:
   1. Se arr[mid] == target, retornar mid
   2. Se arr[mid] < target, atualizar left = mid + 1
   3. Se arr[mid] > target, atualizar right = mid - 1
4. Repetir: Retornar ao passo 2 enquanto left <= right
5. Se o elemento não for encontrado: Retornar -1

Implementação iterativa da busca binária em Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Exemplo de uso:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 7 encontrado no índice 3

2.3 Complexidade de tempo da busca binária O(log n)

A busca binária tem complexidade de tempo O(log n), onde n é a quantidade de elementos no array. Isso significa que a cada passo o algoritmo divide a quantidade de elementos pela metade, o que acelera significativamente a busca em comparação com a busca linear, que tem complexidade de tempo O(n).

Análise da complexidade de tempo:

• Melhor caso (Best case): O elemento é encontrado no primeiro passo, O(1).
• Caso médio (Average case): O(log n).
• Pior caso (Worst case): O elemento é encontrado no último passo ou está ausente, O(log n).

Exemplo para análise da complexidade de tempo:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado no índice {index}")  # Saída: Elemento 7 encontrado no índice 3

# O algoritmo executou 3 passos (logaritmo de 7 elementos) para achar o elemento, 
# o que corresponde a O(log n)

Representação gráfica da complexidade:

Imagine um array de 16 elementos.

Suponha que estejamos procurando o elemento 15, então os passos seriam:

Primeiro passo. Verifica o elemento do meio (restam 8 elementos).

Segundo passo. Verifica o elemento do meio na metade restante (restam 4 elementos).

Terceiro passo. Verifica o elemento do meio na metade restante (restam 2 elementos).

Quarto passo. Verifica o último elemento (resta 1 elemento).

O algoritmo realiza 4 passos para um array de 16 elementos, o que corresponde ao logaritmo de base 2 de 16, ou seja, log2(16) = 4. Essa é a complexidade logarítmica O(log n).