The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number.
std::lower_boundReturns an iterator pointing to the first element in the range [first,last) which does not compare less than val . The elements are compared using operator< for the first version, and comp for the second.
set::lower_bound() function in C++ STL If the key passed in the parameter exceeds the maximum value in the container, then the iterator returned points to the element beyond last element in the set container. Time Complexity of set::lower_bound() is O(logn), where n is the size of the set.
lower_bound in c++ stl returns an iterator even when the element is not present.
In a sorted container, the last element that is less than or equivalent to x
, is the element before the first element that is greater than x
.
Thus you can call std::upper_bound
, and decrement the returned iterator once.
(Before decrementing, you must of course check that it is not the begin iterator; if it is, then there are no elements that are less than or equivalent to x
.)
Here is a wrapper function around upper_bound which returns the largest number in a container or array which is less than or equal to a given value:
template <class ForwardIterator, class T>
ForwardIterator largest_less_than_or_equal_to ( ForwardIterator first,
ForwardIterator last,
const T& value)
{
ForwardIterator upperb = upper_bound(first, last, value);
// First element is >, so none are <=
if(upperb == first)
return NULL;
// All elements are <=, so return the largest.
if(upperb == last)
return --upperb;
return upperb - 1;
}
For a better explanation of what this is doing and how to use this function, check out:
C++ STL — Find last number less than or equal to a given element in an array or container
I have test your reverse iterator solution, it is correct.
Given v
is sorted by '<'
Find last element less than x:
auto iter = std::upper_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
std::cout<<"no found";
else
std::cout<<*iter;
Find last element less than equal x:
auto iter = std::lower_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
std::cout<<"no found";
else
std::cout<<*iter;
This is better than iter -= 1
version
std::prev
: https://en.cppreference.com/w/cpp/iterator/prev
#include <iostream>
#include <map>
int main()
{
std::map<int, char> m{{2, 'a'}, {4, 'b'}, {6, 'c'}, {8, 'd'}, {10, 'e'}};
int num = 3;
auto it = m.upper_bound(num);
auto pv = std::prev(it);
std::cout << "upper bound of " << num << ": "
<< it->first << ", " << it->second << '\n';
std::cout << "lower than or equal of " << num << ": "
<< pv->first << ", " << pv->second << '\n';
}
Output:
upper bound of 3: 4, b
lower than or equal than 3: 2, a
A simple implementation in Python:
def bi_search(arr, target):
"""
index of the last element which <= target
"""
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo - 1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With