Binary search: halving the search space in O(log n)

You know the slow way to find a name in a phone book: start at page one and turn pages until you find it. With a thousand pages, the worst case is a thousand page-turns. The fast way is to open to the middle, check whether the name comes before or after it, and discard the half you do not need. A thousand pages becomes 500, then 250, then 125. After ten halvings, one page remains. That is binary search. It turns a linear scan into a logarithmic one. This article explains the idea behind the site’s Binary Search problem, with special attention to the boundary where most implementations fail.

The one requirement: the data must be sorted

Binary search only works when the thing you are searching is sorted. The method depends on one fact: after you inspect the middle element, everything to its left is smaller and everything to its right is larger. You can then discard half the array after one comparison. Unsorted data provides no such information. The middle element does not tell you where anything else is, so sort the data first or use a structure that guarantees order, such as a binary search tree, which its article covers.

Use this recognition rule: sorted array (or sorted answer space) plus a “find it” question equals binary search. The site’s Two Sum II gives you a sorted array and a target. Validate Binary Search Tree gives you a tree whose nodes follow the same ordering rule. The problems look different, but the move is the same.

The move: look at the middle, discard half

The algorithm is a loop over three numbers: left, right, and the middle between them. Each pass computes the middle index, compares the element there to the target, and keeps only the half that could still contain the target:

• middle equals the target → return it.
• middle is less than the target → the target must be to the right, so move left past middle.
• middle is greater than the target → the target must be to the left, so move right before middle.

Run it on the site’s public example - nums = [-1, 0, 3, 5, 9, 12], target = 9:

left=0  right=5  middle=2  nums[2]=3   3 < 9  → left=3
left=3  right=5  middle=4  nums[4]=9   9 == 9 → return 4

Two comparisons replace five. Each comparison halves the window, so the number of comparisons is the number of times you can halve $n$ before reaching one element: log_2 n. The What O(n) actually promises article provides the vocabulary: linear is $n$, halving is $\log n$, and for a million elements that means a million comparisons versus about twenty.

The Elixir shape is a tail-recursive search over the window:

defmodule Solution do
  def binary_search(nums, target) do
    search(nums, target, 0, length(nums) - 1)
  end

  defp search(_nums, _target, left, right) when left > right, do: -1

  defp search(nums, target, left, right) do
    middle = div(left + right, 2)
    value = Enum.at(nums, middle)

    cond do
      value == target -> middle
      value < target -> search(nums, target, middle + 1, right)
      true -> search(nums, target, left, middle - 1)
    end
  end
end

The when left > right clause handles the not-found case: the window is empty, so the target was never there. The other clauses implement the three-way comparison above.

The trap is the boundary

Every binary search bug is a boundary bug. The key question is whether the loop runs while left <= right or while left < right. Match that condition to the way you shrink the window. If you move left to middle + 1 and right to middle - 1 (as above), use left <= right. When left and right meet on one element, you still need to check it before the window becomes empty. The site’s one-element test (nums = [5], target = 5) catches the implementation that skips that element and wrongly returns “not found.”

Two smaller traps matter. The midpoint must use integer division: div(left + right, 2) in Elixir, never a floating-point (left + right) / 2 that produces a non-integer index. In languages with fixed-width integers, left + right can overflow before the division. Use left + div(right - left, 2) instead. Elixir’s bignums make this a non-issue, but that overflow risk is why C-family textbooks use the defensive form.

Binary search on the answer, not the array

The thing you search does not have to be an array index. It can be an answer. A question of the form “what is the smallest $x$ for which f(x) is true?” can use binary search when f(x) is monotone: once f(x) becomes true, it stays true. The search space is the range of possible answers, not the array. The comparison “is the middle a valid answer?” replaces “is the middle the target?”. The minimum-platforms problem in the catalog uses this form: binary-search the number of platforms, then check whether that number suffices. The recognition rule - “the answer space is sorted, and f is monotone” - is the same class-recognition move the Algorithms past the interview article names as the whole skill.

Where to go next

• Binary Search - the direct problem, including the one-element boundary case.
• Two Sum II - Sorted Input - the same halving move on a sorted-array target search.
• Validate Binary Search Tree - binary search’s data-structure home: the ordering that makes the halving valid.
• What a comparison is worth - why the log in $O(\log n)$ is inescapable for comparison-based search.
• Binary trees - where the halving structure becomes a data structure instead of an array index.
• What O(n) actually promises - the $n$ versus $\log n$ shape change.

Binary search comes down to one move: sorted data tells you where the answer cannot be, so discard half the space and repeat. The algorithm is three lines. The boundary is the hard part, and the one-element window is where the bugs hide.