Binary Search in C++

Part two of **Runnable Notes** - snippets that run in the browser. **Binary search** finds a value in a sorted array in `O(log n)`: keep a window `[lo, hi]`, test the middle, throw away the half that cannot contain the target, repeat until the window is empty or you hit it.

The loop

1int binarySearch(const std::vector<int>& a, int target) {
2    int lo = 0;
3    int hi = (int)a.size() - 1;
4    while (lo <= hi) {
5        int mid = lo + (hi - lo) / 2;
6        if (a[mid] == target) {
7            return mid;
8        } else if (a[mid] < target) {
9            lo = mid + 1;
10        } else {
11            hi = mid - 1;
12        }
13    }
14    return -1;
15}

The array must be sorted - that is the precondition that makes discarding a half safe.

The mid-update trap

The single most common binary-search bug is not excluding `mid` when narrowing. Use `lo = mid` instead of `lo = mid + 1` and, when the target sits in the upper half of a two-element window, `lo` never advances - the loop never terminates and the playground kills it after 5 seconds:

lo = mid + 1;   // mid was tested: skip past it
hi = mid - 1;

Always shrink strictly past the element you just tested.

Run it

The program reads `n`, then `n` sorted integers, then a `target`, and prints the index (0-based) or `-1`. Run it here:

A run on a 5-element array, searching for `5`:

stdout
2

Try it

stdin is `n`, then the array, then the target:

| stdin | expected stdout | |-------|-----------------| | `5` / `1 3 5 7 9` / `5` | `2` | | `5` / `1 3 5 7 9` / `1` | `0` | | `5` / `1 3 5 7 9` / `9` | `4` | | `5` / `1 3 5 7 9` / `6` | `-1` | | `1` / `5` / `5` | `0` |

Next in the series: **Longest Increasing Subsequence** - from `O(n^2)` DP to the `O(n log n)` patience variant.