rationale for std::lower_bound and std::upper_boun

Question

STL provides binary search functions std::lower_bound and std::upper_bound, but I tend not to use them because I've been unable to remember what they do, because their contracts seem completely mystifying to me.

Just from looking at the names, I'd guess that "lower_bound" might be short for "last lower bound",
i.e. the last element in the sorted list that is <= the given val (if any).
And similarly I'd guess "upper_bound" might be short for "first upper bound",
i.e. the first element in the sorted list that is >= the given val (if any).

But the documentation says they do something rather different from that-- something that seems to be a mixture of backwards and random, to me. To paraphrase the doc:
- lower_bound finds the first element that's >= val
- upper_bound finds the first element that's > val

So lower_bound doesn't find a lower bound at all; it finds the first upper bound!? And upper_bound finds the first strict upper bound.

Does this make any sense?? How do you remember it?

Answer 1

If you have multiple elements in the range [first, last) whose value equals the value val you are searching for, then the range [l, u) where

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

is precisely the range of elements equal to val within the range [first, last). So l and u are the "lower bound" and "upper bound" for the equal range. It makes sense if you're accustomed to thinking in terms of half-open intervals.

(Note that std::equal_range will return both the lower and upper bound in a pair, in a single call.)

Answer 2

Imagine what you would do if you want to find the first element equal to val in [first, last). You first exclude from first elements which are strictly smaller than val, then exclude backward from last - 1 those strictly greater than val. Then the remaining range is [lower_bound, upper_bound]

Answer 3

I accepted Brian's answer, but I just realized another helpful way of thinking about it which adds clarity for me, so I'm adding this for reference.

Think of the returned iterator as pointing, not at the element *iter, but just before that element, i.e. between that element and the preceding element in the list if there is one. Thinking about it that way, the contracts of the two functions become symmetric: lower_bound finds the position of the transition from <val to >=val, and upper_bound finds the position of the transition from <=val to >val. Or to put it another way, lower_bound is the beginning of the range of items that compare equal to val (i.e. the range that std::equal_range returns), and upper_bound is the end of them.

I wish they would talk about it like this (or any of the other good answers given) in the docs; that would make it much less mystifying!

Answer 4

For an array or vector :

std::lower_bound: Returns an iterator pointing to the first element in the range that is

• less than or equal to value.(for array or vector in decreasing order)
• greater than or equal to value.(for array or vector in increasing order)

std::upper_bound: Returns an iterator pointing to the first element in the range that is

• less than value.(for array or vector in decreasing order)

• greater than value.(for array or vector in increasing order)