Linear & binary search

Linear search checks elements one at a time and works on any sequence — O(n). Binary search checks the middle, throws away the half that cannot contain the target, and repeats — O(log n) — but it only works on data that is sorted and supports jumping to the middle in one step. That second condition is the catch on the BEAM, and it is what sends sorted data into tuples or trees rather than lists.

Searching the sorted array [5, 8, 10, 12, 20, 30, 42] for 20. Select a strategy and watch which elements it touches.

Two ways to find 20 Advanced: binary search needs random access

Two ways to find 20

Linear search walks from the left, comparing each element, until it hits 20 at index 4 — five checks. Binary search starts in the middle and halves: 12 is too small, go right; 30 is too big, go left; 20 — found, in three checks. Select a strategy.

The strategy · select one

cost: O(n) · checks elements one by one — 5 here

result: found 20 at index 4

Both find 20; binary search asks sharper questions. Each comparison it makes discards half of what remains, so it needs about log₂ n of them — three for seven elements, twenty for a million.

Advanced: binary search needs random access

Binary search’s halving assumes you can reach the middle element in one step. On a contiguous structure — a tuple or an :array — elem/2 does that in O(1), so binary search is genuinely O(log n). On a linked list it is a trap: reaching the middle is itself an O(n) walk, so “binary search” over a list is O(n log n) — slower than a plain linear scan. This is why Enum.at/2 on a list is O(n), and why sorted data you intend to search lives in a tuple, not a list.

When you need both fast search and cheap updates, a balanced binary search tree (F4.02) gives O(log n) search without contiguous memory — each step follows one pointer instead of indexing. And when ordering is not required at all, a hash-based map (F4.04) drops the cost to O(1) on average. The structure you choose is the search you can afford.

# linear search — works on any list, O(n)
def linear([x | _], x, i), do: {:ok, i}
def linear([_ | t], x, i), do: linear(t, x, i + 1)
def linear([], _x, _i), do: :error

# binary search — needs O(1) indexing, so a tuple, not a list
def binary(arr, x), do: binary(arr, x, 0, tuple_size(arr) - 1)
defp binary(_arr, _x, lo, hi) when lo > hi, do: :error
defp binary(arr, x, lo, hi) do
  mid = div(lo + hi, 2)
  case elem(arr, mid) do
    ^x -> {:ok, mid}
    v when v < x -> binary(arr, x, mid + 1, hi)
    _ -> binary(arr, x, lo, mid - 1)
  end
end

The idea

Sorted data lets each comparison discard half — but only if you can reach the middle in one step.

In Elixir

Binary search wants a tuple (elem/2 is O(1)); a list forces O(n), a tree gives O(log n).

Next: stability & sort cost — ranking the sorts, and the lower bound none of them can beat.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Merge sort — Wikipedia — a stable functional sort.
Cormen, Leiserson, Rivest & Stein (2022). Introduction to Algorithms (4th ed.) — sorting and searching, in depth.