lower_bound and upper_bound

Tried to use stl lower_bound and upper_bound today and noticed that I didn’t quite understand them correctly before.

The corresponding leetcode problem

Some notes on these:

For std::lower_bound(T k), it returns the first element that is greater or equal to k.

For std::upper_bound(T k), it returns the first element that is greater than k.

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cassert>
#include <map>
#include <iostream>

using namespace std;

int main() {
    map<int, int> hm {{1, 1}, {3, 3}, {5, 5}, {7, 7}};
    map<int, int>::iterator it;
    // it == hm.end() because there does not exist a value in hm that is >= 8.
    it = hm.lower_bound(8);
    if(it == hm.end()) {
        cout << "Can't find a value >= 8..." << endl;
    } else {
        assert(0);
    }
    // it points to {7, 7}.
    it = hm.lower_bound(7);
    cout << "lower_bound for 7: " << it->first << endl;
    // it == hm.end() because there does not exist a value in hm that is > 7.
    it = hm.upper_bound(7);
    if(it == hm.end()) {
        cout << "Cannot find a value > 7..." << endl;
    } else {
        assert(0);
    }
    // it points to {5, 5}.
    it = hm.lower_bound(5);
    cout << "lower_bound for 5: " << it->first << endl;
    // it points to {7, 7}.
    it = hm.upper_bound(5);
    cout << "upper_bound for 5: " << it->first << endl;	
    return 0;
}

If we want to find a value in std::map that is strictly less than a given key k, we can do the following:

1
2
3
4
5
6
7
auto it = hm.lower_bound(k);
if(it == hm.begin()) {
    cout << "Can't find a value that is strictly less than k!" << endl;
} else {
    --it;
    cout << "The value that is strictly less than k is: " << it->first << endl;
}

Note that if we provide custom comparator to std::map for example, we need to make sure that the comparator returns true only for the cases where lhs < rhs for std::lower_bound to work correctly. This is the same for std::upper_bound. ref