Study
C++ · DSA: binary search
Binary search by hand with the overflow-safe midpoint, then std::lower_bound, upper_bound and binary_search.
- Binary search halves the search range each step, so it needs O(log n) comparisons, but only on sorted data.
- lower_bound returns the first position where the value could be inserted without breaking the order.