Binary Search Algorithm

Problem

Given a sorted array $A$ of $n$ elements and a target value, find the index of the target (or determine it is not present).

KEY TAKEAWAY: Binary search works by repeatedly halving the search space. It requires the input to be sorted. Time complexity: $O(\log n)$.

Algorithm

ALGORITHM BinarySearch(A, target)
    low ← 0
    high ← length(A) - 1

    while low <= high do
        mid ← (low + high) / 2   // integer division
        if A[mid] = target then
            return mid
        else if A[mid] < target then
            low ← mid + 1        // target is in right half
        else
            high ← mid - 1       // target is in left half
        end if
    end while

    return -1    // target not found

Worked Example

Array: $A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]$, Target: 23

Complexity Analysis

Recurrence: $T(n) = T(n/2) + O(1)$

• $a = 1$, $b = 2$, $c = 0$
• $\log_b a = \log_2 1 = 0 = c$ → Master Theorem Case 2
• $T(n) = O(n^0 \log n) = O(\log n)$

Comparison to linear search:

Preconditions

• Array must be sorted in ascending order
• Direct indexed access required (array, not linked list)

Design Pattern

Binary search is an example of the Divide and Conquer pattern:
1. Divide: Find the midpoint; compare target with middle element
2. Eliminate: Discard the half that cannot contain the target
3. Recurse: Search remaining half

Recursive Version

def binary_search(A, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if A[mid] == target:
        return mid
    elif A[mid] < target:
        return binary_search(A, target, mid + 1, high)
    else:
        return binary_search(A, target, low, mid - 1)

Correctness

Loop invariant: If the target is present, it lies in $A[low..high]$.
- Initially: $A[0..n-1]$ — the entire array
- Maintained: Each iteration correctly narrows the range based on the comparison
- Termination: low > high means target is absent

EXAM TIP: Binary search requires a sorted input — always state this precondition. If asked to trace, show the values of low, high, and mid at each step.