algorithms · high

Binary Search

Binary search locates a target in a sorted array by checking the middle element and discarding the half that cannot contain the target, halving the search space each step for O(log n) time. The classic bugs are off-by-one loop bounds and computing the midpoint as (lo+hi)/2, which can overflow — use lo + (hi-lo)/2.

The code

int binarySearch(int a[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids (lo+hi) overflow
        if (a[mid] == target)
            return mid; // found it
        else if (a[mid] < target)
            lo = mid + 1; // search the right half
        else
            hi = mid - 1; // search the left half
    }
    return -1; // not present
}

What this lesson walks through

1. 01Binary search — needs a SORTED array
2. 02a[3] = 4 < 7 — go right
3. 03a[5] == 7 — found

Binary search finds a target in a sorted array by repeatedly halving the search window: check the middle, then keep only the half that could contain the target. Here we search for 7.