📚 Post 3: A Santa Graal da Busca: O(log N)

Acelerando a Busca: Por que o O(log N) (Busca Binária) é mais rápido que a Luz? ✨

Vimos nos posts anteriores como migrar de O(N^2) para O(N). Mas e se pudéssemos ser ainda mais rápidos?

A complexidade O(log N) (Logarítmica) é o padrão-ouro para qualquer algoritmo de busca. A grande diferença é a taxa de crescimento:

Tamanho da Entrada (N)	O(N) (Linear)	O(log N) (Logarítmico)
1.000	1.000 passos	10 passos
1.000.000	1.000.000 passos	20 passos
1.000.000.000	1 bilhão de passos	aproximadamente 30 passos

O tempo de execução é quase indiferente ao tamanho da entrada.

---

O Segredo: Dividir para Conquistar 🔪

O algoritmo que atinge essa velocidade é a Busca Binária (Binary Search). A lógica é simples: em cada passo, você consegue descartar metade do espaço de busca.

Pré-requisito Obrigatório

Para que a Busca Binária funcione, a estrutura de dados DEVE estar ordenada.

1. Você verifica o elemento central (mid).
2. Se o valor central for menor que seu alvo, você descarta toda a metade esquerda.
3. Se for maior, descarta toda a metade direita.

Isso se repete recursivamente, dividindo o problema ao meio (log2) a cada iteração.

---

O Desafio O(N) em Elixir 💥

Aqui está a pegadinha para quem programa em Elixir:

Como a Lista Ligada padrão só sabe onde a cabeça está, se você tentar acessar o elemento central (o índice N/2) em uma lista de Elixir, o sistema é forçado a percorrer os N/2 elementos, tornando essa operação O(N).

Se a cada passo da sua busca O(log N) você gasta O(N) para encontrar o meio, a complexidade final se torna O(N log N) no melhor dos casos, o que anula o ganho da Busca Binária!

A Solução em Elixir: Tuplas O(1)

Para realizar a Busca Binária corretamente em O(log N), precisamos de uma estrutura que permita acesso por índice em O(1). No ecossistema Erlang/Elixir, usamos Tuplas para essa finalidade.

Com o acesso O(1) garantido, podemos implementar a lógica recursiva:

defmodule BinarySearch do
  @doc "Inicia a Busca Binária O(log N)."
  def search(list, target) do
    # Conversão para Tupla para simular o acesso O(1) por índice
    array = List.to_tuple(list)
    # Inicializa a recursão: low=0, high=N-1
    binary_search_recursive(array, target, 0, tuple_size(array) - 1)
  end

  # Condição de Falha: low cruzou high. Target não existe.
  defp binary_search_recursive(_array, _target, low, high) when low > high do
    :not_found
  end

  # Condição Recursiva Principal
  defp binary_search_recursive(array, target, low, high) do
    # 1. Calcular o índice central (mid)
    mid = floor((low + high) / 2)

    # 2. Obter o valor central (acesso O(1) na tupla)
    # Tuplas em Erlang são base 1, por isso o + 1
    current_value = :erlang.element(mid + 1, array) 

    # 3. Condição de Sucesso
    if current_value == target do
      mid # Retorna o índice

    # 4. Alvo é MAIOR: Descartamos a esquerda, movemos low
    else if current_value < target do
      binary_search_recursive(array, target, mid + 1, high)

    # 5. Alvo é MENOR: Descartamos a direita, movemos high
    else 
      binary_search_recursive(array, target, low, mid - 1)
    end
   end
  end
end

A beleza dessa função é que ela demonstra a complexidade O(log N) de forma perfeita, pois as chamadas recursivas sempre reduzem o espaço de busca pela metade.

---

Próxima Parada: O Padrão Ouro

Se O(log N) é o melhor para a busca, qual é o melhor para a Ordenação?

No próximo post, exploraremos a complexidade O(N log N) (Linearithmic), o padrão-ouro dos algoritmos de ordenação, e desvendaremos o Merge Sort, que combina o poder logarítmico de dividir problemas com o trabalho linear de mesclá-los de volta.