mercredi 27 octobre 2021

What is the change I need to make to perform reverse of upper_bound?

I feel lower_bound in c++ stl is not the opposite of the upper_bound function. By default, in a non-decreasing array, if I use upper_bound and if the element is found and it is not the last element in the sorted array, then the next element > passed element is given and if the element is then last element or not found, then end() iterator returned. The following C++ code can be used to test this.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int
main ()
{
  vector<int> arr{-973, -808, -550, 301, 414, 897};
  auto p = upper_bound (arr.begin (), arr.end (), 301);
  if (p != arr.end ())
    cout << *p << endl;
  else
    cout << "end" << endl;
  return 0;
}
// Output: 414

But now I need the opposite thing. I need the smaller element from the matched element to be returned. In the above example, if I pass 301, then, I want to get -550 in return. Currently, I am using the following code and it seems to work for the given example but I am not sure if it is the right code or I need to implement it manually using binary search.

auto p = upper_bound(arr.rbegin(), arr.rend(), 301, greater<int>());

PS. I am using if (p != arr.rend ()) for this.

Aucun commentaire:

Enregistrer un commentaire