Insight Vault

Binary Search

4 min read

Binary search repeatedly halves a sorted search space. It is one of the first algorithms where the structure of the input changes the whole cost.

The usual time complexity is O(log n) because each step discards about half of the remaining candidates.

Core Idea

Binary search keeps a range of possible positions. It checks the middle value, then decides whether the answer must be on the left side, on the right side, or at the middle.

The input must support a reliable ordering. For a normal value search, the array must be sorted.

The key invariant is: if the target exists, it is still inside the current search interval. Every update to left or right must preserve that statement.

Function Contract

binary_search(values, target) expects values to be sorted in ascending order and target to be comparable with the list elements.

It returns an index where target appears, or -1 if the target is absent. If duplicates exist, this exact version returns some matching index, not necessarily the first or last one.

first_true(left, right, condition) expects condition(index) to be monotonic over the integer range. Once the condition becomes true, it must stay true for larger indexes.

Python Example

def binary_search(values, target):
    left = 0
    right = len(values) - 1
 
    while left <= right:
        mid = (left + right) // 2
 
        if values[mid] == target:
            return mid
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return -1

The interval [left, right] is the remaining search space.

Step-by-Step Trace

Search for 14 in:

[2, 5, 8, 11, 14, 19, 23]

The initial interval is indexes 0..6. The middle index is 3, and values[3] is 11. Since 11 < 14, every value at index 3 or earlier is too small, so left becomes 4.

The interval is now 4..6. The middle index is 5, and values[5] is 19. Since 19 > 14, every value at index 5 or later is too large, so right becomes 4.

The interval is now 4..4. The middle value is 14, so the algorithm returns index 4.

Binary search can also find a boundary, such as the first index where a condition becomes true:

def first_true(left, right, condition):
    answer = None
 
    while left <= right:
        mid = (left + right) // 2
        if condition(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
 
    return answer

This works only when the condition is monotonic: once it becomes true, it stays true.

Failure Example

Binary search fails on unsorted input because the comparison no longer proves which half can be discarded. In [10, 1, 7], seeing 1 in the middle does not prove that every value on the left is smaller or every value on the right is larger.

The algorithm is not about the physical middle alone. It is about a middle check that safely removes half of the remaining candidates.

Common Confusions

Binary search is not only for finding an exact value. It can also find the first position where a condition becomes true, if the condition is monotonic.

Off-by-one errors are common. The loop condition and the updates to left and right must match the chosen interval convention.

Binary search is invalid if the remaining candidates cannot be safely cut in half. If the input is unsorted and no monotonic condition exists, discarding half the candidates may discard the answer.

When To Use It

Use binary search when the candidates are ordered and each check can safely discard half of them. It is useful for sorted arrays, answer-space search, and boundary-finding problems.

When writing it, name the invariant in plain language. For exact search, the invariant is that the target, if present, remains between left and right.

The Main Point

Binary search is valid only when the remaining candidates can be cut in half without losing the answer. Sorted order or a monotonic condition is the real requirement.

Backlinks

Graph

Depth 1