Binary search with returned index in STL?
This code should work fine
auto itr = lower_bound(v.begin(), v.end(), key) ;
index = distance(v.begin(), itr);
More about std::lower_bound() - https://www.geeksforgeeks.org/stdlower_bound-in-c/
Clearly, this "will return the bitwise complement" is a big deal for you and I do not understand what you mean. That said, lookup std::upper_bound and see if it does what you want.
There is no simple STL method which returns index against a sorted vector as far as I know, however you can use sample function below:
/**
* @param v - sorted vector instance
* @param data - value to search
* @return 0-based index if data found, -1 otherwise
*/
int binary_search_find_index(std::vector<int> v, int data) {
auto it = std::lower_bound(v.begin(), v.end(), data);
if (it == v.end() || *it != data) {
return -1;
} else {
std::size_t index = std::distance(v.begin(), it);
return index;
}
}
I'm quite certain the standard library doesn't include anything to do precisely what you're asking for.
To get what you want, you'll probably want to start from std::lower_bound
or std::upper_bound
, and convert the iterator it returns into an index, then complement the index if the value wasn't found.
lower_bound
will find the position of the first item with that value (if any).upper_bound
will find the position of the last item with that value (again, if any).- Both will return an iterator to the next larger item if the specified value isn't present (or
.last()
if there is no larger item).