Binary Search

Binary search finds a target value in a sorted sequence by repeatedly dividing the search space in half. At each step, it compares the target with the middle element and discards half of the remaining elements.

This reduces the problem size exponentially, which leads to logarithmic time complexity.

Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$ A[i] = x $$

If no such index exists, return $-1$.

Key Idea

Maintain a search interval $[l, r]$. At each step:

• Compute midpoint $m$
• Compare $A[m]$ with $x$
• Eliminate half of the interval

Algorithm

binary_search(A, x):
    l = 0
    r = length(A) - 1

    while l <= r:
        m = l + (r - l) // 2

        if A[m] == x:
            return m
        else if A[m] < x:
            l = m + 1
        else:
            r = m - 1

    return -1

Example

Let

$$ A = [1, 3, 5, 7, 9, 11] $$

and

$$ x = 7 $$

Steps:

step	l	r	m	A[m]	action
1	0	5	2	5	move right
2	3	5	4	9	move left
3	3	3	3	7	found

Return index $3$.

Correctness

At each step, the algorithm maintains the invariant:

• If $x$ exists in $A$, then it must lie within $[l, r]$

Each comparison removes half of the remaining candidates while preserving this invariant. When $l > r$, the interval is empty, so $x$ does not exist.

Complexity

case	comparisons	time
best	$1$	$O(1)$
worst	$\lfloor \log_2 n \rfloor + 1$	$O(\log n)$
average	$O(\log n)$	$O(\log n)$

Space complexity:

• Iterative: $O(1)$
• Recursive: $O(\log n)$ due to call stack

Requirements

Binary search requires:

• The array must be sorted
• Random access to elements

If either condition fails, correctness or efficiency breaks.

Common Variants

Binary search generalizes to:

• Lower bound (first $\ge x$)
• Upper bound (first $> x$)
• First true in monotone predicate
• Search on answer space

These variants rely on the same invariant: monotonicity.

Implementation

def binary_search(a, x):
    l, r = 0, len(a) - 1
    while l <= r:
        m = l + (r - l) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

func BinarySearch(a []int, x int) int {
    l, r := 0, len(a)-1
    for l <= r {
        m := l + (r-l)/2
        if a[m] == x {
            return m
        } else if a[m] < x {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return -1
}