Find lower and upper bounds
Return a boundary first; decide separately whether it is an exact match.
Understand the idea
Lower bound is the first index whose value is at least x; upper bound is the first index whose value is greater than x. Both may return n. Keep a half-open candidate interval [lo, hi), and discard a half only when its values cannot contain the boundary.
Trace a small example
In [1, 2, 2, 2, 5], lower(2) = 1 and upper(2) = 4, so 2 occurs three times. The number of values in [L, R] is upper(R) − lower(L). Finding lower(4) = 4 does not mean 4 exists: a[4] is 5.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> a{1, 2, 2, 4, 4, 8};
auto first = std::lower_bound(a.begin(), a.end(), 2);
auto last = std::upper_bound(a.begin(), a.end(), 4);
std::cout << last - first << '\n';
}Conditions and cost
The range must be sorted under the same comparison. Guard index < n before reading a returned position. Each search is O(log n); sorting once for q queries gives O(n log n + q log n).
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
What is lower_bound([2, 4, 4, 9], 10) as a zero-based index?
Turn the idea into code
Count values in the inclusive range [2, 4] in [1, 2, 2, 4, 4, 8].
Give me a hint
Find the first value ≥ 2 and the first value > 4.
Show the explained solution
The boundaries are 1 and 5, giving 5 − 1 = 4 values.
Your notes
Mark complete when you can explain it yourself.