Binary search in C++ is a foundational algorithm that lets you locate a target value inside a sorted collection by repeatedly halving the search range. This approach dramatically reduces the number of comparisons compared to linear scanning, making it ideal for performance critical code.
When implemented correctly with C++ standard library tools or manual loops, binary search delivers predictable logarithmic time complexity and integrates smoothly with containers like arrays, vectors, and iterators. The following sections detail how it works, where to use it, and how to avoid common pitfalls.
| Term | Definition | Complexity | Requirement |
|---|---|---|---|
| Binary Search | Divide and conquer search on a sorted range | O(log n) | Sorted data |
| std::binary_search | Standard library predicate returning true if value exists | O(log n) | Sorted range, comparable elements |
| std::lower_bound | Iterator to the first position where value can be inserted without breaking order | O(log n) | Sorted range, optional comparator |
| std::upper_bound | Iterator to the first position greater than the value | O(log n) | Sorted range, optional comparator |
| Custom Implementation | Handwritten loop or recursion matching problem specifics | O(log n) | Manual boundary and midpoint handling |
Preconditions for Using Binary Search
Binary search in C++ requires random access iterators and a monotonic ordering. If the range is not sorted according to the same comparison used during the search, the result is undefined.
Prefer std::sort before invoking std::binary_search, lower_bound, or upper_bound. For custom types, supply a comparator that establishes a strict weak ordering to keep behavior predictable.
Core Mechanics and Loop Invariants
At each step the algorithm maintains a search interval [left, right). By comparing the target to the midpoint element, it discards half of the remaining candidates. A well defined loop invariant ensures correctness and termination.
In a typical while loop, left never decreases and right never increases, preserving the invariant that the target, if present, must lie inside the interval. When left meets right, the search concludes efficiently.
Using the C++ Standard Library
The standard library provides std::binary_search, std::lower_bound, and std::upper_bound in the <algorithm> header. These functions work with vectors, arrays, and any container offering random access iterators.
Leveraging these routines reduces boilerplate and leverages carefully tuned implementations, while still allowing custom comparators for descending order or user defined types.
Implementing Binary Search Manually
Writing your own version helps you adapt the pattern to specialized problems, such as searching in rotated arrays or locating floating point thresholds.
- Initialize left and right boundaries based on inclusive or exclusive indexing
- Compute midpoint carefully to avoid overflow, using
left + (right - left) / 2 - Narrow the interval based on comparison results, updating left or right consistently
- Validate postconditions, especially when the target is absent
Best Practices and Performance Tips
Writing correct and efficient binary search code involves attention to boundary conditions, comparator design, and iterator usage.
- Always ensure the range is sorted with the same comparison you use for search
- Prefer standard library functions to minimize off by one errors
- Use
left + (right - left) / 2to prevent integer overflow on large indices - Test edge cases like empty ranges, duplicates, and targets at the ends
- Choose iterative implementations for production code to control stack usage
FAQ
Reader questions
Does binary search in C++ work on unsorted data?
No, binary search requires the data to be sorted according to the same ordering used during the search. Applying it on unsorted data leads to unpredictable results.
What is the difference between lower_bound and upper_bound?
lower_bound returns an iterator to the first position where the value could be inserted without violating order, while upper_bound returns the first position strictly greater than the value.
Can binary search be implemented recursively in C++?
Yes, you can implement it recursively, but iterative versions are usually preferred in C++ to avoid extra stack overhead and potential depth limits on large ranges.
How do I use binary search with custom objects?
Define a comparator that establishes a strict weak ordering, then pass it to std::binary_search , lower_bound , or upper_bound , or implement manual comparisons against a member field.