📚 포스트 3: 검색의 성배: O(log N)

Source: Dev.to

O(log N)이 선형 탐색보다 빠른 이유

이전 글에서는 O(N²) 에서 O(N) 로 어떻게 전환할 수 있는지 살펴보았습니다. 하지만 우리는 더 빠르게 갈 수 있습니다. O(log N) (로그) 복잡도는 입력 크기에 거의 영향을 받지 않는 성장률 때문에 모든 탐색 알고리즘의 금본위 기준입니다.

이 속도를 구현하는 알고리즘은 이진 탐색입니다. 각 단계마다 남은 탐색 공간의 절반을 버립니다.

이진 탐색 개요

이진 탐색은 정렬된 자료 구조에서만 동작합니다. 과정은 다음과 같습니다.

1. 중간 요소(mid)를 확인합니다.
2. 중간 값이 목표보다 작으면 왼쪽 절반을 버립니다.
3. 중간 값이 목표보다 크면 오른쪽 절반을 버립니다.
4. 매 반복마다 문제를 절반으로 줄이며(log₂) 재귀적으로 반복합니다.

Elixir에서의 함정

Elixir의 기본 연결 리스트는 머리만 알고 있습니다. 인덱스 N/2에 있는 요소에 접근하려면 런타임이 N/2개의 요소를 순회해야 하므로 O(N) 이 됩니다. 각 이진 탐색 단계가 중간을 찾는 데 O(N) 비용이 든다면 전체 복잡도는 O(N log N) 가 되어 이점이 사라집니다.

Erlang/Elixir 생태계에서 진정한 O(log N) 를 얻으려면 O(1) 인덱스 접근이 가능한 자료 구조가 필요합니다. 튜플이 바로 그 역할을 합니다.

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

이 함수는 각 재귀 호출이 탐색 공간을 절반으로 줄이면서 중간 요소에 상수 시간으로 접근하기 때문에 진정한 O(log N) 동작을 보여줍니다.

다음 주제는?

O(log N) 가 탐색에 최적의 복잡도라면, 정렬에 대한 최적의 복잡도는 무엇일까요? 다음 글에서는 O(N log N) (선형 로그) 알고리즘을 살펴볼 예정이며, 병합 정렬에 초점을 맞춰 로그 기반 분할‑정복 전략과 선형 병합 작업을 결합하는 방식을 다룰 것입니다.