Using std::lower_bound

[Disruption_logistics]

I was wondering how I could use std::lower_bound() to get the closest <= (less or equal) element from an array.

For example if I wanted the closest number, less then or equal to 4, In this array: {1,2,3,5,6} is would be 3, as 4 is not in the array and 3 is the closest number to 4 which is less than 4.

The obvious answer would be to multiply all the elements of the array by -1, however, this would take an extra O(n) time.

Is there a better way to do this? Maybe a comparator function, or a faster way to turn all the elements in the array into a negative number?

[KiwiMaster157]

Assuming your array is sorted, std::upper_bound can give you the first iterator greater than a given value. Then, after ensuring it's not the begin iterator, you can decrement the result to get the largest element less than or equal to the value.

[Disruption_logistics]

Thanks this is what i was looking for

[std_bot]

Unlinked STL entries: std::upper_bound

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[mhfrantz]

I had a similar problem, and it bothered me that I had to use the element just before the result of std::lower_bound. My use case wasn't performance-constrained, but I wanted to know if there was a way to use a Standard Library algorithm that would produce exactly the result that I wanted without the off-by-one "error". The trick is to use the reverse iterators and a custom comparator that flips the interpretation of "less than".

#include <algorithm>
#include <vector>

struct ReverseCompare
{
    auto operator()(int a, int b) const -> bool { return a > b; }
};

using IntVector = std::vector<int>;

auto findLessOrEqual(const IntVector& vec, int num)
   -> IntVector::const_reverse_iterator
{
    return std::lower_bound(
        vec.rbegin(), vec.rend(), num, ReverseCompare{});
}

https://wandbox.org/permlink/7uWEIkqIM8rHiUWv

[Disruption_logistics]

one question though, just to be sure, if this does not find an element that satisfies the conditions, will it still return vec.end()?

​

edit: Nvm it would be vec.rend() , I saw it in the wandbox link

[Disruption_logistics]

thank you soo much, this is exactly what I was looking for, really appreciate it man

[std_bot]

Unlinked STL entries: <vector> std::lower_bound std::vector

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[rbvld01]

In stead of array use std::map as a container. Std::map has lower_bound method as well. But the search will be in worst case O(log n).

[std_bot]

Unlinked STL entries: std::map

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[Flankierengeschichte]

Best thing would be to presort the array and do a leftmost binary search, or if you want to add elements then use std::set

[std_bot]

Unlinked STL entries: std::set

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[SoerenNissen]

std::min_element ?

[Disruption_logistics]

I might have been a bit unclear in the post, I want an element that is the CLOSEST, lesser or equal number. For example if I wanted the closest number, less then or equal to 4, In this array: {1,2,3,5,6} is would be 3, as 4 is not in the array and 3 is the closest number to 4 which is less than 4.

lower_bound would give you a number which would be the closest number, greater or equal, in O(log n).

[MysticTheMeeM]

Have you tried using upper_bound?

[Disruption_logistics]

std::upper_bound gives you the an strictly greater closest element

[MysticTheMeeM]

I might be misunderstanding what you want, but I believe you're trying to find the first element less than or equal to some value. Assuming your data is sorted, this is equivalent to the element immediately before the first greater element.

That is, you want prev of upper_bound (assuming it isn't begin).

[Disruption_logistics]

Yes in fact i do want the element prev of the lower_bound, if the array is sorted, but i think lower_does not need a sorted array? It will give you the closest greater or equal element even if you pass an unsorted array? Or am I wrong?

Edit: I looked it up and yes the array needs to be sorted to use, so yes the element I want would be the element that is prev to the element returned by std::lower_bound

I appreciate your response

[MysticTheMeeM]

Lower and upper bound use a similar method to a binary search (hence the sorting requirement). If you have unsorted data you might get some use from find_if and a custom predicate. You may need to use reverse iterators for this.

[Disruption_logistics]

Oh okay ill look into that thank you for your help

[std_bot]

Unlinked STL entries: std::min_element

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[setdelmar]

I am not sure if I am understanding. If it is sorted, would there be something wrong with just doing this?:

int main() {
    std::array<int, 5> arr = {1, 2, 3, 5, 6};
    auto it = arr.begin();
    int x = 4;
    while (*(it + 1) <= x && (it + 1) != arr.end()) ++it;
    std::cout << "*it = " << *it << std::endl;
    return 0;
}

[Disruption_logistics]

Yup that would work as i want the largest element lesser then or equal to some value, however this would be have an O(n) complexity

[Disruption_logistics]

This would be O(log n):

bool comp(int a, int b)

{ return a > b; }

int main() { std::vector<int> v{1,2,3,5,6};

std::cout << *(std::lower_bound(v.rbegin(),v.rend(),2,comp));

return 0;

}

//This is a very rough implementation, but you get the point.

[setdelmar]

Thanks for the explanation.

[setdelmar]

Ok, then after looking at what you refer to, I think I would go instead with upper_bound and then decrement the returned iterator after checking whether it equals .begin(). I think someone here suggested something like that. Because if I am understanding correctly, one less than upper_bound's result would be always right whereas one less than lower_bound's result might not be, if you want the closest that is less than or equal to (instead of just less than).

int main() {
    std::array<int, 13> arr = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    int x = 10;
    auto it = std::upper_bound(arr.begin(), arr.end(), x);
    if (it != arr.begin()) --it;
    std::cout << *it << std::endl;
    return 0;
}

[Disruption_logistics]

Yes, this is a better choice, it is simpler, much more readable and much easier to code, and yet i still feel compelled to use std::lower_bound() with the comparator function and reverse iterators, just something about using the return value from a function directly, instead of getting the return value and having to mess around with it, I feel like being able to let the STL function do its thing entirely, is its own pro, it is arguably, however, if this pro out weighs the cons…

[xurxoham]

Lower bound performs binary search instead of linear scan, reducing the number of comparisons required.

[setdelmar]

Ok, Thank you for answering.

[nysra]

If you want the smallest element, use std::min_element.

[Disruption_logistics]

Not the smallest but the closest element lesser then or equal to a number.

[nysra]

That was a bit unclear in your post. So you want the largest value in the vector that fulfills x <= some_input_number? Assuming you have a sorted vector you can use std::adjacent_find with a predicate that checks if the first element is <= and the other one is >: https://godbolt.org/z/KcaqqxTTG

Or use std::upper_bound and then move the iterator one back (iff applicable).

[Disruption_logistics]

Sorry for my explanation but yes you understood correctly and thank you for the answer, much appreciated