C++ - index of element in sorted std::vector

Question

I have an std::vector that I know is sorted. Using std::binary_search I can find whether an element is in the vector in log time. Unfortunately std::binary_search doesn't return the index of the element in the vector in case of success (or if it does I don't know how to access it). std::find will give me an iterator to the element but it doesn't use the fact that the vector is sorted so it runs in linear time and not log time. I know I can trivially implement my own binary search algorithm but I want to know if there is a way to do this in the standard.

Answer 1

You can use std::lower_bound (O(log(N)) and std::distance (O(1) for random access iterators):

auto lower = std::lower_bound(v.begin(), v.end(), val);
// check that value has been found
const bool found = lower != v.end() && *lower == val;

Then, either

auto idx = std::distance(v.begin(), lower);

or plain arithmetic:

auto idx = lower - v.begin();

Answer 2

You want to use the lower_bound() function. It's a little bit funky to make it generally useful, but serves the purpose you want.

Answer 3

Use equal_range, not lower_bound.

You can’t simply check if the iterator returned by std::lower_bound is different from the end to know whether the element is in the collection. If the element is not present, std::lower_bound returns the location where it should have been, not the end of the collection.

See: https://www.fluentcpp.com/2017/01/16/how-to-stdfind-something-efficiently-with-the-stl/