binary search
Binary search finds a value in a sorted list by repeatedly halving the region where it could be. Look at the middle element: if it's your target, you're done; if your target is smaller, throw away the whole upper half; if larger, throw away the lower half. Each look discards half of what's left. It's exactly how you find a word in a dictionary — you don't read page 1, you flip to the middle and decide which way to go.
The mechanism is a shrinking window described by two indices, low and high, with mid = (low + high) / 2 in between. Each comparison moves low up or high down so the window keeps closing, and the search ends when the value is found or the window is empty (low > high). The one non-negotiable requirement is that the data be sorted by the key you're comparing — on unsorted data the 'throw away half' reasoning collapses.
Halving repeatedly is why it's so fast: from n items you reach a single candidate in about log2(n) steps — O(log n) time, O(1) extra space. A million items take only about twenty comparisons. The trade-off is that you must keep the data sorted (and in a structure with fast random access, like an array); for a one-off lookup in unsorted data, plain linear search may be simpler.
int binarySearch(const std::vector<int>& a, int target) {
int low = 0, high = (int)a.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) low = mid + 1; // go right
else high = mid - 1; // go left
}
return -1; // not found
}Each step halves the search range, so a sorted array of n needs only ~log2(n) comparisons.
Write mid = low + (high - low) / 2 rather than (low + high) / 2; on very large arrays the latter can overflow when low + high exceeds the integer limit. This was a famous bug in many textbook implementations.