The FBB::binary_search function templates extend the STL binary_search function template returning an iterator to the element found, instead of a bool value informing the caller whether or not the searched for element is present in a provided iterator range.
The bool value returned by the STL binary_search function template is often not the kind of information the caller of the function is interested in. Rather, the caller will often want to use binary_search in the way find_if is used: returning an iterator to the found element or returning the end-iterator if the element was not found. Whereas find_if does not require the elements in the iterator range to be sorted, and thus will use a linear search binary_search may use the sorted nature of the elements to its advantage, using a binary search algorithm requiring 2 log N iterations to locate the searched for element rather than (on average) N/2 iterations. The FBB::binary_search algorithm uses this binary searching process while at the same time allowing its use like find_if.
Since the FBB::binary_search function templates use the same number and types of parameters as the stl::binary_search function templates the explicit use of the FBB namespace will often be required in situations where both function templates are made available to the compiler.
#include <iostream> #include <string> #include "../binarysearch" using namespace std; using namespace FBB; string words[] = { "eight", // alphabetically sorted number-names "five", "four", "nine", "one", "seven", "six", "ten", "three", "two" }; class Comparator { public: bool operator()(string const &left, string const &right) const; }; inline bool Comparator::operator()(string const &left, string const &right) const { return left < right; } bool compFun(string const &left, string const &right) { return left < right; } int main() { string *ret = binary_search(words, words + 10, "five"); if (ret != words + 10) cout << "five is at offset " << (ret - words) << endl; ret = binary_search(words, words + 10, "grandpa"); if (ret == words + 10) cout << "grandpa is not the name of a number\n"; ret = binary_search(words, words + 10, "five", Comparator()); if (ret != words + 10) cout << "five is at offset " << (ret - words) << endl; ret = binary_search(words, words + 10, "grandpa", compFun); // or use: Comparator() if (ret == words + 10) cout << "grandpa is not the name of a number\n"; return 0; }