What function in std library exists for binary vector search and element search?

Question

I have a node struct

struct Node{CString text, int id;}; 

in sorted vector.

I am wondering if there is a function in the algorithm that will perform a binary search of the vector and find the element.

Answer 1

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

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

For these objects, operator< must be implemented for these algorithms to work.

Answer 2

Yes, there is a function called "binary_search" std :: binary_search

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

See here for a sample.

Combine this with the Martin York statement and you should be fine (alternatively, you could write a predicate functor

Answer 3

Instead of a sorted vector <Node> Why not use a map. This is a sorted container. Thus, any search performed in this case through std :: find () automatically has the same properties as a binary search.

Answer 4

Use std::equal_range to find the range of elements in a sorted vector. std::equal_range returns a std::pair iterators, giving you a range in the vector of elements equal to the argument you provide. If the range is empty, then your element is not in the vector, and the length of the range indicates how many times your element is displayed in the vector.

Here is an example of using int 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 do this with struct Node , you either need to provide an operator < for the struct Node , or pass the std::equal_range value in the comparator. You can do this by providing lambda as an argument to std::equal_range to compare your structures.

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