How to find the first smaller element than an integer X in a vector ? (c++)

Question

If I have the following vector {10 10 10 20 20 20 30 30} and I want a function to return the position of the integer that = X or directly the smaller element after X , like for example if I am searching for 11 I want the function to return 2 since the 2nd element(10) is the first smaller element than 11 in the vector.
I tried using lower_bound but that doesn't work.

int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
vector<int>::iterator low,up;

sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

low=lower_bound (v.begin(), v.end(), 11); //
up= upper_bound (v.begin(), v.end(), 11); //

cout << "lower_bound at position " << int(low- v.begin()) << endl;
cout << "upper_bound at position " << int(up - v.begin()) << endl;

return 0;

this code outputs:

lower_bound at position 3
upper_bound at position 3

Titos

But position 2 isn't the first element smaller than 11 in your example. It's the last element smaller. Maybe upper_bound() - 1 but really you need to be clear about exactly what you want and code it appropriately. – Goalie

Is your vector always sorted? Or is that just a coincidence? – Phelloderm

Answer 1

cppreference informs me that std::lower_bound

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

and std::upper_bound

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

In this case, given a vector containing 10 10 10 20 20 20 30 30 I would expect both functions to point at the first 20, which sits at position 3 in the vector and is indeed the result you got both times. If you had instead asked for 20, std::lower_bound would return an iterator pointing to the first 20 in the vector (position 3)... the first number not less than 20 and the same result you'd get when asking for 11. In this case though, std::upper_bound would return an iterator pointing at the first 30 (position 6), which is the first value greater than 20.

Just move the iterator back one to get the last value less than your target number, std::prev is one way to do that.

Chaparral

Answer 2

Well, upper_bound returns the first item that is greater than the test item, so the one before that (if it exists) will be the one you want?

Laywoman

I think that solves it .. a small question why did lower_bound return 20 here ? – Titos

@LoersAntario see the documentation for lower_bound, which I quoted in my answer ;-) – Chaparral

Answer 3

you could do this...it might be better to return an iterator in case if the vector is empty...

auto find_next_smaller(vector<int> vec, const int x) { 
    std::sort(vec.begin(), vec.end());
    auto it = std::lower_bound(vec.begin(), vec.end(), x); 
    if (it == vec.end()) { 
      it = (vec.rbegin()+1).base();
    }
    else if (it != vec.begin() && *it > x) { 
        --it; 
    }

    return it; 
} 

Carder

Answer 4

If one has to find an element less than or equal to some x then multiset can be used to do so.

#include <iostream> 
#include <set> 
#include <iterator> 

using namespace std; 

int main() 
{
    multiset <int, greater <int> > iammultiset;
    iammultiset.insert(10);
    iammultiset.insert(10);
    iammultiset.insert(14);
    iammultiset.insert(20);
    iammultiset.insert(20);
    iammultiset.insert(30);
    iammultiset.insert(40);
    iammultiset.insert(50);
    //{10,10,14,20,20,30,40,50}
    
    cout<<*iammultiset.lower_bound(17) << endl;
    //The Output here will be 14.
    
    cout<<*iammultiset.lower_bound(20) << endl;
    //The Output here will be 20.
}

Jugglery

Answer 5

#include <bits/stdc++.h>
using namespace std;
template <typename F, typename T>

F first_less_than(F f, F l, T val)
{
    auto it = lower_bound(f, l, val);
    return it == f ? l : --it;
}

int main()
{
    vector<int> s{10, 20, 25, 40};
    auto j = first_less_than(s.begin(), s.end(), 35);

    cout << *j;

    //output : 25
    return 0;
}

Yellowtail

Your answer could be improved by adding more information on what the code does and how it helps the OP. – Newcomer

Answer 6

I used greater comparator along with reverse iterator

#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
vector<int>::reverse_iterator low;
vector<int>::iterator up;

sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

low=lower_bound (v.rbegin(), v.rend(), 11, greater<int>()); //
up= upper_bound (v.begin(), v.end(), 11); //
cout <<"lower_bound number "<<*low<<endl;
cout << "lower_bound at position " << int(v.rend()-low)-1 << endl; //subtracted 1 bcz we used rend() iterator(as in end() iterator we subtract 1 to get position)
cout << "upper_bound at position " << int(up - v.begin()) << endl;

return 0;
}

Output:

lower_bound number 10
lower_bound at position 2
upper_bound at position 3

Textbook