The Sneaky difference between lower_bound and upper_bound

std::lower_bound(first, last, value); // first element >= value
std::upper_bound(first, last, value); // first element > value

In the code above the difference is small enough to miss, and big enough to cause browser bugs. Welcome to the world of lower_bound and upper_bound. Why do I say that? Let's take an example. Say there is a sorted vector:

std::vector<int> values = {0, 10, 19};

Searching for 14 makes both functions point to the same value:

std::lower_bound(values.begin(), values.end(), 14); // 19
std::upper_bound(values.begin(), values.end(), 14); // 19

14 is not in the vector, so the first value that is greater than or equal to 14 is 19, so lower_bound results in 19. And the first value that is greater than 14 is also 19, hence upper_bound results in 19 too.

So far, they look the same. But wait for it... let's take an example value that is already present in the vector:

std::lower_bound(values.begin(), values.end(), 10); // 10
std::upper_bound(values.begin(), values.end(), 10); // 19

lower_bound can stop at 10, because it is looking for the first value that is >= 10. upper_bound skips 10, because it is looking for the first value that is strictly > 10. That is literally the whole trick. If you are not familiar with C++, the names may not immediately suggest that.

But again one would ask what happens if vector has duplicates, so let's take an example:

std::vector<int> values = {2, 4, 4, 4, 8};

lower_bound(4) points to the first 4. upper_bound(4) points to 8, the first value after all the 4s. Together they give the range of all matching values:

auto lower = std::lower_bound(values.begin(), values.end(), 4);
auto upper = std::upper_bound(values.begin(), values.end(), 4);

// The range [lower, upper) contains all the 4s. So {4, 4, 4}
// "[" means lower is included and ")" means upper is excluded.

And the count is:

std::distance(lower, upper); // 3

That is why these two functions often appear as a pair. lower_bound finds where matching values begin. upper_bound finds where they end. In short:

lower_bound: first >= value
upper_bound: first > value

One character of difference, >= vs >, makes the whole story of lower_bound and upper_bound. It is often surprising how many bugs this small piece of logic has caused.

Stay tuned to hear how this caused a bug in your browser! Next blog coming soon!