Binary Search Visualization
Halving a search space sounds trivial until you write it and the loop never ends. The algorithm is four lines; the hard part is the boundary arithmetic, which is why almost everyone gets it wrong at least once. Watching lo, hi and mid change on every pass makes the failure modes obvious in a way that reading the code never does.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int binarySearch(vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
cout << binarySearch(a, 23) << endl;
cout << binarySearch(a, 7) << endl;
return 0;
}Classic inclusive-bounds binary search: it returns the index of 23 (which is 5) and -1 for 7, which is absent.
How it works, step by step
The invariant does the work
At every moment, if the target exists it lies inside a[lo..hi]. Every line in the loop is written to preserve that one sentence. If you ever break it, the search silently returns -1 for values that are actually present.
Probe the middle, not the front
mid splits the live range in half. Comparing a[mid] to the target tells you which half can still contain it, so one comparison eliminates the other half entirely — that is where the log n comes from.
Move past mid, never onto it
When a[mid] < target, the answer cannot be at mid, so lo becomes mid + 1. Setting lo = mid instead leaves mid inside the range forever and the loop stops shrinking.
lo <= hi is the termination condition
The range is inclusive on both ends, so lo == hi still holds exactly one candidate and must be checked. The loop ends when lo passes hi, meaning the live range is empty and the target is absent.
Why mid is computed that way
lo + (hi - lo) / 2 is arithmetically the same as (lo + hi) / 2 but never overflows, because hi - lo fits in an int even when lo + hi would not. On a 10-element array it makes no difference; on indices near 2 billion it does.
Complexity
Each iteration discards half the remaining range, so the loop runs at most log2(n) times; it degrades to useless (not slow — wrong) the instant the input is not sorted by the same comparison the branches use.
Common bugs
The lo = mid infinite loop
Writing lo = mid instead of lo = mid + 1 hangs the program whenever hi == lo + 1: mid rounds down to lo, the condition picks the upper half, and lo is reassigned to the value it already had. Nothing changes and the loop spins forever. Run it in DryRun and you see lo, hi and mid freeze at the same three numbers on frame after frame — that repeated state is the bug, and it is much faster to spot than to reason about.
int hi = a.size() - 1 on an empty vector
size() returns an unsigned type, so 0 - 1 wraps to a huge value before the conversion to int. On an empty vector you get an enormous or negative hi and then an out-of-bounds read at a[mid]. Cast first: int hi = (int)a.size() - 1.
Using < instead of <= in the loop condition
With inclusive bounds, while (lo < hi) skips the final one-element range. The search returns -1 for any target that happens to land at the last surviving index — it works on most test cases and fails on a few, which is the worst kind of bug.
Searching data that is not actually sorted
Binary search does not detect unsorted input; it just returns -1 or the wrong index. This bites hardest when you sort by one key (say, by name) and then search by another (by id). Print or inspect the array right before the call rather than trusting the sort you wrote three functions earlier.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why does binary search need a sorted array?
Because the algorithm throws away half the array based on a single comparison, and that decision is only valid if order guarantees where the target can be. If a[mid] < target in a sorted array, every element left of mid is also smaller, so none of them can match. In unsorted data that inference is false and you discard elements that may contain the answer.
Why is binary search O(log n)?
Each iteration halves the number of candidates: n, then n/2, then n/4, and so on. The number of halvings needed to reach a single element is log2(n), so a million-element array takes about 20 comparisons instead of a million.
What causes an infinite loop in binary search?
An iteration that fails to shrink the range. The usual culprit is lo = mid or hi = mid instead of mid + 1 or mid - 1, which lets mid stay inside the live range when lo and hi are adjacent. Every path through the loop must strictly reduce hi - lo.
Should I use lo + (hi - lo) / 2 or (lo + hi) / 2?
Use lo + (hi - lo) / 2. The two are mathematically identical, but (lo + hi) can overflow a signed int when both indices are large, producing a negative mid and an out-of-bounds access. This is the bug that sat in the JDK binary search for nearly a decade.
Can binary search work on a linked list?
Not usefully. Binary search depends on O(1) random access to reach mid; in a linked list, walking to the middle costs O(n), so each of the log n steps becomes linear and you end up slower than a plain scan.