c++binary-searchupperbound

C++ STL Algorithms upper_bound() that is not strictly greater

Unlike lower_bound, upper_bound does not return an iterator to the element if it compares equivalent to value, but only if it compares strictly greater.

Is there an alternative if I want an upper_bound algorithm that is greater than or equal to.

Solution

  • You could decrease the iterator by 1.

    auto begin = ...;
auto end = ...;
auto it = std::upper_bound(begin, end, target);
if (it == begin)
  return it;
-- it;
if (*it < target)
  return ++it;
else
  return it;

    The position of the iterator will be like this, assume you are searching for 2:

    1 1 1 2 2 2 2 3 3 3 3
      ^     ^ ^
      lb    | ub
            this function


1 1 1 1 3 3 3 3
        ^
        lb & ub & this function