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.