Step 2 of 6

Binary search

In a sorted array, binary search finds a value in O(log n) by halving the search range each step. A million elements takes at most 20 steps.

lo = 0, hi = n - 1
while lo <= hi:
    mid = lo + (hi - lo) / 2      (not (lo + hi) / 2: that can overflow!)
    if v[mid] == target: found
    if v[mid] < target: lo = mid + 1
    else: hi = mid - 1

Binary search is famously easy to get subtly wrong. Off-by-one errors in lo/hi cause infinite loops or missed elements. Write it carefully once and understand every + 1 and - 1.

Your turn: write int find_index(const std::vector<int>& v, int target) returning the index of target in the sorted vector v, or -1. Don't use the standard library's search functions.

Previous: Big-O in practice Next: lower_bound and upper_bound