Find the nearest valid key
Translate thresholds into lower bounds, upper bounds, and predecessors.
The equality boundary
For ascending keys, lower_bound(x) finds the first key at least x; upper_bound(x) finds the first key strictly greater than x. Both return end() when no suitable key exists. In {2, 5, 9}, lower_bound(5) finds 5 and upper_bound(5) finds 9. For missing key 8, both find 9.
Use the container’s member operation: values.lower_bound(x). A generic std::lower_bound on set iterators may perform logarithmically many comparisons but still make linear iterator movements. The member bound gives logarithmic search.
Step backward only when there is a predecessor
To find the largest key ≤ x, locate upper_bound(x), then step back if the result differs from begin(). To find the largest key < x, start from lower_bound(x) instead. The guard is about begin(), because a backward step needs an earlier element.
When a nonempty set’s bound equals end(), stepping back is valid. When the set is empty, begin() and end() coincide, so the same begin() guard handles it safely.
// Complete C++23 program. Input: n q, n keys, then q thresholds.
#include <iostream>
#include <set>
int main() {
int n, q;
std::cin >> n >> q;
std::set<int> values;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
values.insert(x);
}
while (q--) {
int x;
std::cin >> x;
auto it = values.upper_bound(x);
if (it == values.begin()) std::cout << "NONE\n";
else { --it; std::cout << *it << '\n'; }
}
}A range of values is not a range of indices
For L ≤ R, the keys in inclusive value interval [L, R] are the iterator range from lower_bound(L) to upper_bound(R), excluding the latter. Finding both endpoints costs O(log(d + 1)); visiting k results adds O(k). Printing thousands of values is not a logarithmic operation.
std::distance(begin(), lower_bound(x)) correctly counts smaller set keys, but may walk a linear number of entries. If many changing-rank queries are required, the GNU order-statistics tree introduced later is a different tool.
Set & multiset
Both containers keep values sorted. Erase one removes a single occurrence, like erase(iterator).
3 stored items · 3 distinct values
Guided simulation · Change the inputs to test your understanding.
For {3, 6, 10}, which operation starts the search for the greatest key at most 6?
Turn the idea into code
Find the greatest key ≤ each threshold 1, 5, 8, 20 in {2, 5, 9}. Then give the inclusive iterator range for keys from 3 through 8.
Give me a hint
Separate the boundary that is too large from the affordable predecessor.
Show the explained solution
The predecessor answers are NONE, 5, 5, 9. The value interval uses [lower_bound(3), upper_bound(8)); it visits only 5. The backward guard handles the first query, and a nonempty end() boundary handles the last.
Your notes
Mark complete when you can explain it yourself.