Qual algoritmo tem uma complexidade logarítmica O(log n)?

O algoritmo de busca binária (ou dicotômica) tem uma complexidade temporal logarítmica O(log n).

Princípio de funcionamento da busca binária:

1. Requer um array (ou lista) ordenado.
2. A cada passo, compara o elemento procurado com o elemento no meio do intervalo de busca atual.
3. Se os elementos coincidirem, a busca termina.
4. Se o elemento procurado for menor que o do meio, a busca continua na metade esquerda do intervalo.
5. Se o elemento procurado for maior que o do meio, a busca continua na metade direita do intervalo.
6. O intervalo de busca é reduzido pela metade a cada passo.

Exemplo de implementação em Python:

# Função de busca binária
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Elemento encontrado, retorna o índice
        elif mid_val < target:
            low = mid + 1  # Ignora a metade esquerda
        else:
            high = mid - 1  # Ignora a metade direita

    return -1  # Elemento não encontrado

# Exemplo de uso
# lista_ordenada = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# valor_objetivo = 23
# resultado = binary_search(lista_ordenada, valor_objetivo)
# if resultado != -1:
#     print(f"Elemento encontrado no índice: {resultado}")
# else:
#     print("Elemento não encontrado")

A complexidade logarítmica deve-se ao fato de que a quantidade de operações é proporcional ao logaritmo do tamanho dos dados de entrada (n), pois a cada passo, o espaço de busca é reduzido pela metade.