Menu
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.
640
You can use the find function, found in the std namespace, ie std::find . You pass the std::find function the begin and end iterator from the vector you want to search, along with the element you're looking for and compare the resulting iterator to the end of the vector to see if they match or not.
To search a target element in a vector we will be using the binarySearch() method of the Collections class. Parameters: The List type object on which binary search is to be performed. The value of the target element.
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. We used binary search in the guessing game in the introductory tutorial.
The simple answer is: std::find for unsorted data and std::binary_search for sorted data.
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.
65
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
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
