Binary search
How binary search finds a value in sorted data in O(log n), how to write it without bugs, and std::lower_bound.
Binary search works on sorted data. Compare the target with the middle element; if the target is bigger, it can only be in the right half, so discard the left half, and vice versa. Each step halves the range, so a million elements take about 20 comparisons.
Classic bugs: computing (lo + hi) / 2 can overflow for huge indexes (use lo + (hi - lo) / 2), and off-by-one loop bounds. In C++, prefer std::lower_bound, which returns the first position not less than the target.
Example
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{2, 5, 8, 12, 16, 23, 38};
auto it = std::lower_bound(v.begin(), v.end(), 16);
bool found = it != v.end() && *it == 16;
std::cout << found << " at index " << (it - v.begin()) << "\n";
return 0;
}
Output:
1 at index 4
Watch it run: Binary search halves the range