Binary search with returned index in STL?

Question

I need a binary search function.

I couldn't find any function in the standard library that will return the index of the found item, and if it wasn't found, will return the bitwise complement of the index of the next element that is larger than the item I looked for.

What is the function I am looking for?

Edit: I need to insert an item to a sorted vector and to keep it sorted. That's why I need to bitwise complement index.

Answer 1

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

Answer 2

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