What function in the std library is there to binary search a vector and find an element?

Question

I've got a node struct

struct Node{CString text, int id;};

in a sorted vector.

I'm wondering if there's a function in algorithm that will do a binary search of the vector and find an element.

Answer 1

std::binary_search() will tell you if a value exists in the container.

std::lower_bound()/std::upper_bound() will return an iterator to the first/last occurrence of a value.

Your objects need to implement operator< for these algorithms to work.

Answer 2

Yes, there's a function called "binary_search" std::binary_search

You give it first, last and a value or a predicate.

See here for a sample

Combine that with Martin York's operator== and you should be OK (alternatively you can write a predicate functor

Answer 3

Rather than a sorted vector<Node>
Why not use a map. This is a sorted container. So any search done on this via std::find() automatically has the same properties as a binary search.

Answer 4

Use std::equal_range to find a range of elements in a sorted vector. std::equal_range returns a std::pair of iterators, giving you a range in the vector of elements equal to the argument you provide. If the range is empty, then your item isn't in the vector, and the length of the range tells you how many times your item appears in the vector.

Here is an example using ints instead of struct Node:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main(int argc, const char * argv[])
{
    std::vector<int> sorted = { 1, 2, 2, 5, 10 };

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
    // Outputs "5 5"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), 5);
    // Outputs "3 4"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), -1);
    // Outputs "0 0"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    return 0;
}

To make this work with struct Node you'll either have to provide an operator < for struct Node or pass in a comparator to std::equal_range. You can do that by providing a lambda as an argument to std::equal_range to compare your structs.

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
                               [](Node lhs, Node rhs) { return lhs.id < rhs.id; });