Binary search: discard half with proof
Search sorted data by maintaining a half-open candidate range and removing half each step.
After this lesson
You should be able to
- State why sorted order is mandatory for binary search.
- Implement binary search without overflow or boundary gaps.
Maintain a candidate interval
Binary search relies on sorted order. Compare the target with a middle element. If the target is smaller, every element at or above the middle can be rejected; if larger, every element at or below it can be rejected.
A half-open range [low, high) contains candidate indexes from low through high−1. It begins as [0, count) and is empty when low == high. This convention makes empty arrays and one-element ranges easier to handle.
size_t binary_search(const int values[], size_t count, int target) {
size_t low = 0;
size_t high = count;
while (low < high) {
size_t middle = low + (high - low) / 2;
if (values[middle] < target) {
low = middle + 1;
} else if (values[middle] > target) {
high = middle;
} else {
return middle;
}
}
return count;
}Every step removes candidates
The invariant is that if the target exists, it remains in [low, high). Each unsuccessful comparison strictly shrinks that interval. Because the candidate count is approximately halved, the number of comparisons grows logarithmically.
middle = low + (high - low) / 2 avoids the overflow risk of (low + high) / 2. Correct boundaries matter more than memorizing a compact version.
Try it yourself
Trace the candidate ranges while searching [2, 5, 8, 12, 16, 23, 38] for 16.
Need a hint?
Start [0,7); middle index 3 contains 12.
Check the worked solution
After 12 < 16, range becomes [4,7). Middle index 5 is 23, so range becomes [4,5). Index 4 is 16.
Quick check
What must be true before using binary search?
Why this lesson exists
Syllabus mapping
Binary search
Maps to course outcomes CO1, CO3, CO6.