Step 3 of 6
lower_bound and upper_bound
In real code, use the standard library's binary searches on sorted ranges. They're correct, fast, and answer more useful questions than "is it there?":
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
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> ages = {12, 15, 15, 15, 18, 21, 30, 42};
auto lo = std::lower_bound(ages.begin(), ages.end(), 15);
auto hi = std::upper_bound(ages.begin(), ages.end(), 15);
std::cout << "15 appears " << (hi - lo) << " times, first at index " << (lo - ages.begin()) << "\n";
auto adults = ages.end() - std::lower_bound(ages.begin(), ages.end(), 18);
std::cout << adults << " are 18 or older\n";
auto pos = std::lower_bound(ages.begin(), ages.end(), 20);
std::cout << "20 would go at index " << (pos - ages.begin()) << ", before " << *pos << "\n";
std::cout << std::binary_search(ages.begin(), ages.end(), 21) << std::binary_search(ages.begin(), ages.end(), 22) << "\n";
}
15 appears 3 times, first at index 1
4 are 18 or older
20 would go at index 5, before 21
10
Picture it
For the value 15 in 12 15 15 15 18:
12 15 15 15 18
^ ^
lower_bound upper_bound
The elements equal to x are exactly [lower_bound, upper_bound). Subtracting the iterators counts them.
Counting a range
The number of values v with lo <= v <= hi is:
upper_bound(hi) - lower_bound(lo)
lower_bound(lo) is the first value that's at least lo; upper_bound(hi) is the first value past hi. Everything between them is in range. Two binary searches, O(log n), no matter how many values match. If lo > hi, the result would be negative, so return 0 in that case.
Your task
Write long count_in_range(const std::vector<int>& sorted, int lo, int hi) counting values v with lo <= v <= hi.
Challenge 2
Write long count_equal(const std::vector<int>& sorted, int x) in O(log n) with std::equal_range, which returns the pair {lower_bound, upper_bound}.
Challenge 3
Write std::vector<int> ranks(const std::vector<int>& sorted_scores, const std::vector<int>& queries). A score's rank is 1 plus the number of scores strictly greater than it, so equal scores share a rank. sorted_scores is in increasing order; use std::upper_bound for each query.