📚 第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)（线性对数）算法，重点介绍 归并排序，它将对数级的分治策略与线性合并工作相结合。