How to find the first smaller element than an integer X in a vector ? (c++)
binary-search, c++, stl, vector
Solution
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.
Problem
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 ```