Binary Search

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.

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.

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.

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.