Binary Search

Phase 1f(x)

The Mathematics

Formal definition, invariant, and complexity analysis

Problem Definition

Given a sorted array $A[0..n-1]$ and a target value $x$ , find the index $i$ such that $A[i] = x$ , or determine that $x$ is not in the array.

A[0] \leq A[1] \leq \cdots \leq A[n-1]

Loop Invariant

At every iteration, if $x$ exists in $A$ , then it must lie within the current search bounds:

A[\text{lo}] \leq x \leq A[\text{hi}]

The search space halves each step. We compute the midpoint and compare:

\text{mid} = \left\lfloor \frac{\text{lo} + \text{hi}}{2} \right\rfloor

$\bullet$ If $A[\text{mid}] = x$ , we found the target.

$\bullet$ If $A[\text{mid}] < x$ , then $\text{lo} \leftarrow \text{mid} + 1$ .

$\bullet$ If $A[\text{mid}] > x$ , then $\text{hi} \leftarrow \text{mid} - 1$ .

Complexity Analysis

Each step does $O(1)$ work and halves the search space. This gives the recurrence:

T(n) = T(n/2) + O(1)

Solving (or by the Master Theorem, case 2 with $a=1, b=2, f(n)=O(1)$ ):

T(n) = O(\log n)

Comparison with Linear Search

Linear search examines each element: $T(n) = O(n)$ . For $n = 1{,}000{,}000$ , binary search needs at most $\lceil \log_2 10^6 \rceil = 20$ comparisons vs. up to $10^6$ for linear search.

Phase 2▶

See It Work

Searching for 23 in a sorted array

A[lo] \leq x \leq A[hi]

Step 1 of 4

Initialize: search for 23 in array of 10 elements. Set lo=0, hi=9.

Phase 3</>

The Code

Bridge from mathematical formulation to Python implementation

Mathematical Formulation

\text{lo} = 0,\; \text{hi} = n-1

Initialize the search bounds to cover the entire array

A[\text{lo}] \leq x \leq A[\text{hi}]

Loop invariant: target must be within current bounds

\text{mid} = \lfloor(\text{lo} + \text{hi})/2\rfloor

Compute the midpoint using integer division

A[\text{mid}] = x \Rightarrow \text{return}

If midpoint value equals target, we found it

A[\text{mid}] < x \Rightarrow \text{lo} = \text{mid} + 1

Target is larger, eliminate the left half

A[\text{mid}] > x \Rightarrow \text{hi} = \text{mid} - 1

Target is smaller, eliminate the right half

Python Implementation

def binary_search(A, x):
    lo, hi = 0, len(A) - 1        # Initialize search bounds
    while lo <= hi:                # Invariant: x in A[lo..hi]
        mid = (lo + hi) // 2      # Compute midpoint
        if A[mid] == x:
            return mid             # Found: return index
        elif A[mid] < x:
            lo = mid + 1           # Eliminate left half
        else:
            hi = mid - 1           # Eliminate right half
    return -1                      # Not found