Why this matters
A shop charges less per item when a customer buys in bulk. Suppose the rule is this: 1 to 9 items cost 10 each, 10 to 19 items cost 9 each, and 20 or more items cost 8 each. A customer orders 25 items. The program must find the rule that covers 25. No rule is stored under the key 25. The program needs the nearest rule that starts at or below 25, which is the rule that starts at 20.
A hash map cannot answer that question. A hash map finds a key only when you ask for that exact key, and it keeps no order between keys. Ask it for 25 and it has nothing to say. The question "which rule is nearest below 25?" needs the keys to be kept in order, so that the program can look at the neighbours of 25.
This lesson covers sorted containers and the lookups they make easy. In Java you will use TreeMap and its methods floorKey and ceilingKey. In C++ you will use lower_bound and upper_bound, which work on a sorted vector. A set and a map have their own member versions. The set, map and unordered_map lesson earlier in this module covers insertion and plain lookup, so this lesson starts from there.
The idea: a sorted line of numbers
Start with no code. Write four numbers in a row, from smallest to largest: 10, 20, 30, 40. Someone asks: what is the nearest value at or below 25? Look along the row. The values 10 and 20 are at or below 25, and 20 is the closer one. So the answer is 20.
The row is the whole idea. Once the values are in order, you can find the answer without reading every value. A method called binary search does this. It looks at the middle value, decides which half could hold the answer, throws the other half away, and repeats. Each check halves the work. Four values need about two checks. A million values need about twenty checks. This is why sorted containers can answer nearest-value questions quickly.
Two words will be used for the rest of the lesson:
- The floor of a number
xis the largest stored value that is less than or equal tox. - The ceiling of a number
xis the smallest stored value that is greater than or equal tox.
Using the row 10, 20, 30, 40:
- The floor of 25 is 20.
- The ceiling of 25 is 30.
- The floor of 20 is 20, because a value equal to
xcounts. - The ceiling of 5 is 10.
- The floor of 5 is no value at all, because nothing stored is that small.
- The ceiling of 45 is no value at all, because nothing stored is that large.
The last two cases are the ones that cause bugs. Every language has to decide what to return when there is no answer. Java returns null. C++ returns a special "end" position. The sections below show both.
Java: TreeMap with floorKey and ceilingKey
A TreeMap is a map that keeps its keys in sorted order. You add a key and a value with put, and read a value with get. Internally it stores the keys in a balanced tree, which is a tree shape that stays even, so every search takes about log n steps. You do not need the tree details to use it. What you need is the promise that the keys stay sorted, and the two methods that use that promise.
floorKey(x)returns the largest key that is less than or equal tox, ornullif there is none.ceilingKey(x)returns the smallest key that is greater than or equal tox, ornullif there is none.
null is Java's word for "no value". It is not a number and not a key. Treat every returned null as a case you must handle.
Worked example 1: the nearest tier
This program stores three tiers in a TreeMap, using the tier's starting key as the key and its name as the value. It then asks the four questions from the sorted row above.
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, String> tiers = new TreeMap<>();
tiers.put(10, "bronze");
tiers.put(20, "silver");
tiers.put(30, "gold");
System.out.println("floorKey(25) = " + tiers.floorKey(25));
System.out.println("ceilingKey(25) = " + tiers.ceilingKey(25));
System.out.println("floorKey(20) = " + tiers.floorKey(20));
System.out.println("ceilingKey(20) = " + tiers.ceilingKey(20));
System.out.println("floorKey(5) = " + tiers.floorKey(5));
System.out.println("ceilingKey(35) = " + tiers.ceilingKey(35));
System.out.println("lowerKey(20) = " + tiers.lowerKey(20));
System.out.println("higherKey(20) = " + tiers.higherKey(20));
System.out.println("tier for 25: " + tiers.get(tiers.floorKey(25)));
}
}Output:
floorKey(25) = 20
ceilingKey(25) = 30
floorKey(20) = 20
ceilingKey(20) = 20
floorKey(5) = null
ceilingKey(35) = null
lowerKey(20) = 10
higherKey(20) = 30
tier for 25: silverRead the output against the rules. floorKey(25) is 20 because 20 is the largest key at or below 25. ceilingKey(25) is 30. When x is itself a key, both methods return x, so floorKey(20) and ceilingKey(20) are both 20. The two null lines are the "no answer" cases: nothing is stored at or below 5, and nothing is stored at or above 35.
The methods lowerKey and higherKey are the strict versions. They never return x itself. lowerKey(20) is 10 and higherKey(20) is 30. Use them when the question is "the one before this key", not "the nearest key, possibly equal".
The last line shows a common pattern. The floor of 25 is a key, so the program can use it with get to read the value stored under that key. Using get with a key that does not exist would return null instead, which is why the floor lookup comes first.
Worked example 2: the price rule for an order
Now the shop problem from the start of the lesson. The rules are stored with the starting quantity as the key and the price per item as the value. For each order, the program finds the rule that starts at or below the quantity, reads its price, and computes the total.
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
// Key: the first quantity a rule applies to. Value: the price per item.
TreeMap<Integer, Integer> priceByStart = new TreeMap<>();
priceByStart.put(1, 10);
priceByStart.put(10, 9);
priceByStart.put(20, 8);
int[] orders = {1, 9, 10, 25, 40};
for (int qty : orders) {
Integer start = priceByStart.floorKey(qty);
int unit = priceByStart.get(start);
System.out.println("qty " + qty + ": rule starts at " + start
+ ", unit price " + unit + ", total " + (qty * unit));
}
}
}Output:
qty 1: rule starts at 1, unit price 10, total 10
qty 9: rule starts at 1, unit price 10, total 90
qty 10: rule starts at 10, unit price 9, total 90
qty 25: rule starts at 20, unit price 8, total 200
qty 40: rule starts at 20, unit price 8, total 320This is the whole job of a tier table. A quantity of 9 falls under the rule that starts at 1, because 10 is not yet at or below 9. A quantity of 10 falls under the rule that starts at 10, because a key equal to the quantity counts. The program never loops over the rules. It asks one question per order, and the sorted keys give the answer.
Notice the declaration Integer start. The method returns an object, not a plain int, because it may return null. Declaring the result as int is the trap covered in the mistakes section below.
C++: lower_bound and upper_bound
C++ has no floorKey or ceilingKey method on a vector. It has two functions that find positions in a sorted range. They are in the <algorithm> header. They take two iterators and a value. An iterator is an object that points at one item in a container, like a bookmark that you can move along. v.begin() points at the first item. v.end() points one position past the last item, to a spot that holds no value. The pair begin() and end() describes a range that includes the start and excludes the end. Programmers call this a half-open range.
Two functions do the work:
lower_bound(first, last, x)returns the position of the first value that is not less thanx. In other words, the first value that is greater than or equal tox.upper_bound(first, last, x)returns the position of the first value that is greater thanx.
If the value is not in the range, both functions return the position where it would be inserted to keep the range sorted. If every value is smaller than x, both return last, which is the end position.
Worked example 1: positions in a sorted vector
This program works on a sorted vector with a repeated value, so the difference between the two functions is visible.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {10, 20, 20, 30, 40};
auto lo = lower_bound(v.begin(), v.end(), 20);
auto hi = upper_bound(v.begin(), v.end(), 20);
cout << "lower_bound(20) at index " << (lo - v.begin()) << endl;
cout << "upper_bound(20) at index " << (hi - v.begin()) << endl;
cout << "copies of 20: " << (hi - lo) << endl;
auto first_ge_25 = lower_bound(v.begin(), v.end(), 25);
cout << "first value >= 25 is " << *first_ge_25 << endl;
auto first_gt_40 = upper_bound(v.begin(), v.end(), 40);
cout << "no value > 40? " << (first_gt_40 == v.end()) << endl;
auto after = upper_bound(v.begin(), v.end(), 25);
if (after != v.begin()) {
cout << "largest value <= 25 is " << *prev(after) << endl;
}
return 0;
}Output:
lower_bound(20) at index 1
upper_bound(20) at index 3
copies of 20: 2
first value >= 25 is 30
no value > 40? 1
largest value <= 25 is 20The vector holds 10, 20, 20, 30 and 40 at indexes 0 to 4. lower_bound(20) stops at index 1, the first 20. upper_bound(20) stops at index 3, the first value after both 20s. The difference between them, 3 minus 1, is the number of copies of 20. This subtraction is the standard way to count matching values in a sorted range.
The line first value >= 25 is 30 uses lower_bound alone. The value 25 is not stored, so the function returns the position of 30, the first value that is at least 25.
The line no value > 40? 1 uses the end position. upper_bound(40) has no value after 40, so it returns v.end(). The comparison with v.end() prints 1, which means true. Always compare with end() before you read a value, because end() holds no value.
The last part finds the largest value at or below 25. upper_bound(25) gives the position of 30, the first value above 25. The item just before that position is 20. The function prev moves an iterator back by one. The check after != v.begin() matters. If 25 were smaller than every value in the vector, upper_bound would return the first position, and prev of the first position would step before the vector. The check prevents that step.
Worked example 2: sets and maps
A set and a map have their own member functions lower_bound and upper_bound. Use the member functions, not the free functions from <algorithm>. The member functions follow the tree and take about log n steps. The free functions can be called on a set's iterators, but they step one position at a time, so they take about n steps.
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
using namespace std;
int main() {
set<int> scores = {10, 20, 30, 40};
auto it = scores.lower_bound(25);
cout << "set lower_bound(25): " << *it << endl;
auto ub = scores.upper_bound(25);
if (ub != scores.begin()) {
cout << "set floor(25): " << *prev(ub) << endl;
}
if (scores.lower_bound(50) == scores.end()) {
cout << "nothing >= 50" << endl;
}
map<int, string> grade = {{10, "D"}, {20, "C"}, {30, "B"}};
auto m = grade.lower_bound(15);
cout << "map lower_bound(15): " << m->first << " " << m->second << endl;
auto m2 = grade.upper_bound(20);
cout << "map upper_bound(20): " << m2->first << " " << m2->second << endl;
return 0;
}Output:
set lower_bound(25): 30
set floor(25): 20
nothing >= 50
map lower_bound(15): 20 C
map upper_bound(20): 30 BThe set answers the same questions as the vector. The ceiling of 25 is 30, the floor of 25 is 20, and a value above every stored key gives the end position.
A map stores a key and a value together. The iterator from lower_bound points at a pair. m->first is the key and m->second is the value. The key 15 is not stored, so lower_bound(15) lands on the key 20, and the program prints 20 with its grade C.
Worked example 3: counting items in a range
The most common use of these functions is counting or listing the items between two limits. Suppose a door sensor records the minute of each opening, in a set. The question is how many openings happened from minute 15 to minute 60, both included.
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
int main() {
// Timestamps (minutes since midnight) of door openings, kept in a set.
set<int> openings = {5, 12, 18, 31, 44, 59, 60, 77, 90};
// Count openings from minute 15 through minute 60, both included.
auto from = openings.lower_bound(15);
auto to = openings.upper_bound(60);
cout << "openings in [15, 60]: " << distance(from, to) << endl;
for (auto it = from; it != to; ++it) {
cout << *it << " ";
}
cout << endl;
// Empty range: nothing between 91 and 100.
cout << "openings in [91, 100]: "
<< distance(openings.lower_bound(91), openings.upper_bound(100)) << endl;
return 0;
}Output:
openings in [15, 60]: 5
18 31 44 59 60
openings in [91, 100]: 0The start is lower_bound(15), which is the first opening at or after minute 15, that is 18. The end is upper_bound(60), which is the first opening after minute 60, that is 77. The range from 18 up to 77, not including 77, holds 18, 31, 44, 59 and 60. That is five items, and distance counts them. The loop prints the same five values.
The range [91, 100] is empty. Both bounds land on the end position, and distance returns 0. An empty result is a normal answer, and the code handles it without a special case.
This pattern works for any sorted container of numbers: timestamps, prices, scores or sizes. The cost is two searches, each about log n steps, plus the work of walking the items you want to print.
Common mistakes and the messages you will see
Mistake 1: calling lower_bound on unsorted data
Both functions assume the range is sorted. If it is not, they still return a position, but the position is wrong, and the compiler and the runtime say nothing.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {30, 10, 40, 20};
auto it = lower_bound(v.begin(), v.end(), 25);
cout << "lower_bound(25) at index " << (it - v.begin()) << endl;
cout << "value " << *it << endl;
cout << "is 25 present? " << binary_search(v.begin(), v.end(), 25) << endl;
return 0;
}Output:
lower_bound(25) at index 2
value 40
is 25 present? 0The true first value that is at least 25 in this vector is 30, at index 0. The function returned 40. The search checked the middle value, 40, saw that it was at least 25, and moved left. Then it checked 10, which is too small, and moved right, and stopped at 40. Because the vector is not in order, the halving steps point the wrong way. The fix is to sort the vector first with sort(v.begin(), v.end()), or to use a container that keeps itself sorted, such as a set.
Mistake 2: using upper_bound alone to find a floor
Learners often try to find the floor of a stored value by stepping back from lower_bound. That gives the wrong answer when the value is stored.
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
int main() {
set<int> s = {10, 20, 30};
auto it = s.lower_bound(20);
cout << "wrong floor(20): " << *prev(it) << endl;
auto ub = s.upper_bound(20);
cout << "right floor(20): " << *prev(ub) << endl;
return 0;
}Output:
wrong floor(20): 10
right floor(20): 20lower_bound(20) lands on 20 itself, so stepping back gives 10. The floor should be 20, because a stored value equal to the question counts. Stepping back from upper_bound gives the right result in both cases. Use upper_bound followed by prev for a floor, and lower_bound for a ceiling.
Mistake 3: passing the free lower_bound a map
The free function std::lower_bound compares each element with a plain value. A map's elements are pairs of a key and a value, so the comparison fails. This program is the smallest version of the mistake.
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, int> m = {{10, 1}, {20, 2}, {30, 3}};
auto it = lower_bound(m.begin(), m.end(), 15);
cout << it->first << endl;
return 0;
}The compiler stops with a long list of notes. The first error line is the one to read, shown here without the long file path in front of it:
error: no match for ‘operator<’ (operand types are ‘std::pair<const int, int>’ and ‘const int’)The message means the compiler cannot compare a pair with a plain number. The fix is the member function: m.lower_bound(15), as in worked example 2 above.
Mistake 4: reading the end position
The end position holds no value. Reading it is undefined behaviour, which means the language makes no promise about what happens. The program may print junk, print a value that looks plausible, or crash. This program reads the end of a set.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {10, 20, 30};
auto it = s.lower_bound(99);
cout << "about to read *it" << endl;
cout << *it << endl;
return 0;
}Output on the machine used for this lesson:
about to read *it
3The program printed 3, which is not in the set. It is not an error message, and it is not the answer to any question. The compiler did not warn about it, and the run gave no error. Another compiler may print a different number. The rule is to compare the result with end() before you read it:
auto it = s.lower_bound(99);
if (it != s.end()) {
cout << *it << endl;
} else {
cout << "none" << endl;
}Mistake 5: storing a null result in an int
In Java, floorKey and ceilingKey return null when no key fits. Assigning that result to an int makes Java try to turn the null into a plain number, and the program stops. This example asks for a floor below the lowest key.
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, String> empty = new TreeMap<>();
int key = empty.floorKey(25);
System.out.println(key);
}
}Output:
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.TreeMap.floorKey(Object)" is null
at Main.main(Main.java:6)The line at Main.main(Main.java:6) names the line that failed. The fix is to declare the result as Integer and check it:
Integer key = empty.floorKey(25);
if (key == null) {
System.out.println("none");
} else {
System.out.println(key);
}Practice
Try each exercise before you open its answer. Each answer lists the expected output.
Exercise 1. A Java TreeMap<Integer, String> holds the keys 5, 15 and 25 with the values "a", "b" and "c". Print floorKey(15), ceilingKey(16) and floorKey(4).
Show the answer
The output is 15, then 25, then null. The key 15 is stored, so its floor is 15. The smallest key at or above 16 is 25. Nothing stored is at or below 4, so the floor is null.
Exercise 2. A C++ vector holds {2, 4, 4, 4, 9}. Use lower_bound and upper_bound to count how many values lie in the range [4, 8], both included.
Show the answer
The output is 3. The code is:
vector<int> v = {2, 4, 4, 4, 9};
auto lo = lower_bound(v.begin(), v.end(), 4);
auto hi = upper_bound(v.begin(), v.end(), 8);
cout << (hi - lo) << endl;lower_bound(4) is index 1, the first 4. upper_bound(8) is index 4, the position of 9. The difference, 4 minus 1, is 3.
Exercise 3. A C++ set<int> holds {1, 3, 5, 7}. Print the largest value at or below 6, and the smallest value at or above 6.
Show the answer
The output is 5 on one line and 7 on the next. The largest value at or below 6 is the value just before upper_bound(6), which is 7, so prev of it is 5. The smallest value at or above 6 is lower_bound(6), which is 7. Code:
set<int> s = {1, 3, 5, 7};
cout << *prev(s.upper_bound(6)) << endl;
cout << *s.lower_bound(6) << endl;Exercise 4. The Java map from exercise 1 has no key at or above 100. The line int k = m.ceilingKey(100); fails. Rewrite the line so that the program prints none in that case.
Show the answer
Declare the result as Integer and check it for null:
Integer k = m.ceilingKey(100);
if (k == null) {
System.out.println("none");
} else {
System.out.println(k);
}The output is none.
Exercise 5. A C++ vector holds {10, 20, 30}. What index does each call return: lower_bound(30), upper_bound(30) and lower_bound(31)? Explain the third answer in one sentence.
Show the answer
The indexes are 2, 3 and 3. lower_bound(30) stops at the 30 itself, index 2. upper_bound(30) stops at the first value after 30, which is the end position, index 3. lower_bound(31) finds no value at or above 31, so it also returns the end position, index 3.
Summary
- A sorted container lets you find the nearest value below or above a number without reading every item.
- In Java,
TreeMap.floorKeyandceilingKeyreturn the nearest key at or below or at or above a value, ornullwhen there is none. - In C++,
lower_boundfinds the first value at or above a value, andupper_boundfinds the first value above it. Use the member functions on asetor amap. - Subtracting two positions from
lower_boundandupper_boundcounts the items in a range. - Always check for the no-answer case:
nullin Java, and the end position in C++. - Sorted containers and sorted ranges must stay sorted. A search on unsorted data gives wrong answers without an error.