Step 3 of 6
lower_bound and upper_bound
In real code, use the standard library's binary searches on sorted ranges:
std::lower_bound(b, e, x): first element not less than x (where x would be inserted)std::upper_bound(b, e, x): first element greater than xstd::binary_search(b, e, x): just yes or no
So the elements equal to x are exactly [lower_bound, upper_bound), and the count of values in a range [lo, hi] is upper_bound(hi) - lower_bound(lo), in O(log n) no matter how many there are.
Your turn: write long count_in_range(const std::vector<int>& sorted, int lo, int hi) counting values v with lo <= v <= hi.