Binary search halves the search space on sorted data—O(log n) time, O(1) space. Also applies to "answer space" monotonic problems (min capacity, max speed).
Template
- Maintain
lo,hiinclusive or half-open—pick one style and stay consistent - Mid avoids overflow:
lo + (hi - lo) / 2 - Compare mid with target; discard half
std::lower_bound
STL lower_bound returns first position not less than value—O(log n) on sorted ranges.
Manual search
#include
#include
#include
int main() {
std::vector a = {3, 5, 7, 9, 11};
int target = 7;
auto it = std::lower_bound(a.begin(), a.end(), target);
if (it != a.end() && *it == target)
std::cout << "found at " << (it - a.begin()) << "\n";
return 0;
} Important interview questions and answers
- Q: Binary search on answer?
A: When feasibility is monotonic in parameter—search parameter space. - Q: Unsorted array?
A: Sort first O(n log n) or use hash map for exact lookup O(n) average.
Self-check
- Why must data be sorted for classic binary search?
- What does lower_bound return?
Tip: Use lo + (hi - lo) / 2 to avoid overflow and impress interviewers.
Interview prep
- Requirement?
Sorted order or monotonic predicate on answer space.
- lower_bound?
First element not less than target—O(log n).