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

Source: Dev.to

Why O(log N) Is Faster Than Linear Search

In previous posts we saw how to move from O(N²) to O(N). But we can go even faster. The O(log N) (logarithmic) complexity is the gold‑standard for any search algorithm because its growth rate is almost independent of the input size.

The algorithm that achieves this speed is Binary Search. At each step it discards half of the remaining search space.

Binary Search Overview

Binary Search works only on sorted data structures. The process is:

1. Examine the middle element (mid).
2. If the middle value is less than the target, discard the left half.
3. If it is greater, discard the right half.
4. Repeat recursively, halving the problem (log₂) each iteration.

The Elixir Gotcha

In Elixir, the default linked‑list only knows the head. Accessing the element at index N/2 forces the runtime to traverse N/2 elements, which is O(N). If each binary‑search step costs O(N) to find the middle, the overall complexity becomes O(N log N), nullifying the benefit.

To achieve true O(log N) in the Erlang/Elixir ecosystem we need a data structure with O(1) indexed access. Tuples provide that.

Implementation in Elixir

defmodule BinarySearch do
  @doc """Starts a binary search with O(log N) complexity."""
  def search(list, target) do
    # Convert the list to a tuple for O(1) index access
    array = List.to_tuple(list)
    # Kick off the recursion: low = 0, high = size - 1
    binary_search_recursive(array, target, 0, tuple_size(array) - 1)
  end

  # Failure condition – low has crossed high, target not found
  defp binary_search_recursive(_array, _target, low, high) when low > high do
    :not_found
  end

  # Main recursive step
  defp binary_search_recursive(array, target, low, high) do
    # 1. Compute the middle index
    mid = div(low + high, 2)

    # 2. Retrieve the middle value (O(1) in a tuple)
    # Tuples in Erlang are 1‑based, so add 1
    current_value = :erlang.element(mid + 1, array)

    # 3. Success condition
    if current_value == target do
      mid
    # 4. Target is greater – discard left half
    else
      if current_value < target do
        binary_search_recursive(array, target, mid + 1, high)
      # 5. Target is smaller – discard right half
      else
        binary_search_recursive(array, target, low, mid - 1)
      end
    end
  end
end

The function demonstrates true O(log N) behavior because each recursive call halves the search space while accessing the middle element in constant time.

What’s Next?

If O(log N) is the optimal complexity for searching, what is the optimal complexity for sorting? In the next post we’ll explore O(N log N) (linearithmic) algorithms, focusing on Merge Sort, which combines the logarithmic divide‑and‑conquer strategy with linear merging work.