Best way to compare elements in a vector and return a object

Question

I have a use case wherein numbers are monotonically increasing in an vector of integers

vec[0] = 2
vec[1] = 5
vec[2] = 8
vec[3] = 10
..

If I am passed number 6, I want to return vec[1], since it lies between vec[1] and vec[2], similarly if passes 9 would have to return vec[2]. My experience with STL is limited , so wanted to check can we solve this with STL or you have to iterate over each by storing the previous and when hit a number greater than the passed number you return

Answer 1

You can use binary search.

Answer 2

There is a binary_search() function in the <algorithm> header. Unfortunately this function only returns a boolean. You could write your own binary search over the sorted vector, that would be faster for large lists than doing the linear search hinted at in your original post. (Apologies if I misread the post).

Answer 3

The STL has four reusable binary search algorithms in the <algorithm> header: lower_bound, upper_bound, equal_range, and binary_search.

lower_bound doesn't do exactly what you want: when the desired element is not present in the sequence, it returns an iterator that refers to the element one past the element that you want. However, you should be able to wrap it with code that implements your behavior without much trouble.