rationale for std::lower_bound and std::upper_bound?

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?

Randall

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.)

Bertold

As a side effect, if items are unique, std::lower_bound is your standard binary search, returning the element if it's in the range, and end() if it is not. – Madelina

several excellent answers appeared almost immediately. this seemed the clearest to me (and the equal_range ref very helpful and exactly appropriate), so accepting. thanks all! – Randall

@MooingDuck std::lower_bound wouldn't necessarily return end() if the element is not in the collection - you get the insertion position of where the element should go. So you need to also check the result for equivalence/equality if aiming to do a binary search lookup. – Merge

The function name omitting the part of equal range causes confusion. – Cuckoopint

Answer 2

std::lower_bound

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.

std::upper_bound

Returns an iterator pointing to the first element in the range [first, last) that is greater than value.

So by mixing both lower and upper bound you are able to exactly describe where your range begins and where it ends.

Does this make any sense??

Yes.

Example:

imagine vector

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                  // ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                           // ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

prints: 4 4 4

---

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

Ectropion

Answer 3

In this case, I think a picture is worth a thousand words. Let's assume we use them to search for 2 in the following collections. The arrows show what iterators the two would return:

So, if you have more than one object with that value already present in the collection, lower_bound will give you an iterator that refers to the first one of them, and upper_bound will give an iterator that refers to the object immediately after the last one of them.

This (among other things) makes the returned iterators usable as the hint parameter to insert.

Therefore, if you use these as the hint, the item you insert will become the new first item with that value (if you used lower_bound) or last item with that value (if you used upper_bound). If the collection didn't contain an item with that value previously, you'll still get an iterator that can be used as a hint to insert it in the correct position in the collection.

Of course, you can also insert without a hint, but using a hint you get a guarantee that the insertion completes with constant complexity, provided that new item to insert can be inserted immediately before the item pointed to by the iterator (as it will in both these cases).

Ibby

Answer 4

Consider the sequence

1 2 3 4 5 6 6 6 7 8 9

lower bound for 6 is the position of the first 6.

upper bound for 6 is the position of the 7.

these positions serve as common (begin, end) pair designating the run of 6-values.

---

Example:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

auto main()
    -> int
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
    auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
    auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
    for( auto it = pos1; it != pos2; ++it )
    {
        cout << *it;
    }
    cout << endl;
}

Incretion

Answer 5

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!

Randall

Answer 6

Both functions are very similar, in that they will find an insertion point in a sorted sequence that will preserve the sort. If there are no existing elements in the sequence that are equal to the search item, they will return the same iterator.

If you're trying to find something in the sequence, use lower_bound - it will point directly to the element if it's found.

If you're inserting into the sequence, use upper_bound - it preserves the original ordering of duplicates.

Infeld

Sounds like good advice, but I don't see that it addresses why the terms "lower_bound" and "upper_bound" make any sense for these operations, for someone who is baffled by the terms and the documentation. – Randall

@DonHatch others have already addressed that question, so sorry if this answer isn't useful for you. I wanted to put this information out there for the Googlers of the future who wonder why you would want to use one vs. the other. – Infeld

Answer 7

the source code actually has a second explanation which I found very helpful to understand the meaning of the function:

lower_bound: Finds the first position in which [val] could be inserted without changing the ordering.

upper_bound: Finds the last position in which [val] could be inserted without changing the ordering.

this [first, last) forms a range which the val could be inserted but still keep the original ordering of the container

lower_bound return "first" i.e. find the "lower boundary of the range"

upper_bound return "last" i.e. find the "upper boundary of the range"

Ladd

Answer 8

Yes. The question absolutely has a point. When someone gave these functions their names they were thinking only of sorted arrays with repeating elements. If you have an array with unique elements, "std::lower_bound()" acts more like a search for an "upper bound" unless it finds the actual element.

So this is what I remember about these functions:

• If you are doing a binary search, consider using std::lower_bound(), and read the manual. std::binary_search() is based on it, too.
• If you want to find the "place" of a value in a sorted array of unique values, consider std::lower_bound() and read the manual.
• If you have an arbitrary task of searching in a sorted array, read the manual for both std::lower_bound() and std::upper_bound().

Failing to read the manual after a month or two since you last used these functions, almost certainly leads to a bug.

Untune

Answer 9

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]

Headreach

Answer 10

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)

Occlude

This is not true, and that's the crux of the question. For an array in decreasing order, std::lower_bound returns "an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found", hence it will either return the very first element or last (depending on whether the value is greater than or less than that first element). Put another way, if the array is decreasing, no subsequent element in the array is going to be greater than value if the first one isn't. – Sigmund