CODEWITHSUNDEEP
c++stlvectorbinary-search
Loers Antario
Loers Antario

Reputation: 1661

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

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

Upvotes: 7

Views: 17888

Answers (6)

Om Raturi
Om Raturi

Reputation: 1

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

Upvotes: 0

Nilesh Kumar Bibhuti
Nilesh Kumar Bibhuti

Reputation: 11

#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;
}

Upvotes: 0

jcoder
jcoder

Reputation: 30035

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?

Upvotes: 3

joshi
joshi

Reputation: 1

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.
}

Upvotes: 0

Gerald
Gerald

Reputation: 133

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; 
}

Upvotes: 0

Rook
Rook

Reputation: 6145

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.

Upvotes: 11

Related Questions