.TH "FBB::binary_search" "3bobcat" "2005\-2020" "libbobcat\-dev_5\&.07\&.00" "Binary search function"

.PP 
.SH "NAME"
FBB::binary_search \- Extensions to the STL binary_search function
template 
.PP 
.SH "SYNOPSIS"
\fB#include <bobcat/binarysearch>\fP
.br 

.PP 
.SH "DESCRIPTION"

.PP 
The \fBFBB::binary_search\fP function templates extend the STL \fIbinary_search\fP
function templates by returning an iterator to the found element, instead of a
\fBbool\fP value informing the caller whether or not the searched for element is
present in a provided iterator range\&.
.PP 
The \fBbool\fP value returned by the STL \fIbinary_search\fP 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 \fIbinary_search\fP in the way
\fIfind_if\fP is used: returning an iterator to an element or returning
the end\-iterator if the element was not found\&. 
.PP 
Whereas \fIfind_if\fP does not require the elements in the iterator range to be
sorted, and therefore uses a linear search, \fIbinary_search\fP benefits from
the sorted nature of the elements using a binary search algorithm requiring
\fI2 log N\fP iterations to locate the searched for element rather than (on
average) \fIN/2\fP iterations\&. The \fIFBB::binary_search\fP algorithm uses this
binary searching process while at the same time allowing it to be used like
\fIfind_if\fP\&.
.PP 
Since the \fIFBB::binary_search\fP function templates use the same number and
types of parameters as the \fIstl::binary_search\fP function templates and
because they are implemented using the \fIstl::lower_bound\fP algorithms the
\fIFBB\fP namespace must explicitly be specified when calling \fIbinary_search\fP\&.
.PP 
.SH "NAMESPACE"
\fBFBB\fP
.br 
All constructors, members, operators and manipulators, mentioned in this
man\-page, are defined in the namespace \fBFBB\fP\&.
.PP 
.SH "INHERITS FROM"
\-
.PP 
.SH "OVERLOADED FUNCTIONS"
In the following description several template type parameters are
used\&. They are:
.IP o 
\fBIterator\fP represents an iterator type; 
.IP o 
\fBType\fP represents a value of the type to which \fIIterator\fP
points\&. 
.IP o 
\fBComparator\fP represents a comparator function or class type object
which was used to sort the elements to which the \fIIterator\fP range refer;

.PP 
.IP o 
\fBIterator binary_search(Iterator begin, Iterator end, Type const
&value)\fP:
.br 
Using a binary search algorithm \fIvalue\fP is searched for in the range
of elements referred to by the provided iterator range\&. If the value is found
an iterator pointing to this value is returned, otherwise \fIend\fP is
returned\&. The elements in the range must have been sorted by the
\fIType\(cq\&s operator<\fP function\&. 
.IP 
.IP o 
\fBIterator binary_search(Iterator begin, Iterator end, Type const
&value, Comparator comparator)\fP:
.br 
Using a binary search algorithm \fIvalue\fP is searched for in the range
of elements referred to by the provided iterator range\&. If the value is found
an iterator pointing to this value is returned, otherwise \fIend\fP is
returned\&. The elements and the provided value are compared using
\fIcomparator(*iterator, value)\fP calls, where \fI*iterator\fP refers to an
object in the provided iterator range\&. The elements in the range must have
been sorted by the \fIComparator\fP function or function object\&.
.IP 
The \fIcomparator\fP function is called with two arguments\&. The first
argument refers to an element in the \fIbegin\&.\&.end\fP range, the second argument
refers to \fIvalue\fP\&.
.IP 
Usually the types of these arguments are identical, but they may
differ\&. Assuming that \fIIterator\fP refers to elements of a type \fIData\fP, then
comparison operators \fIbool operator<(Data const &lhs, Type const &rhs)\fP and
\fIbool operator<(Type const &rhs, Data const &lhs)\fP must both be available\&.

.PP 
.SH "EXAMPLES"
.nf 
#include <iostream>
#include <string>
#include \(dq\&\&.\&./binarysearch\(dq\&

using namespace std;

string words[] = 
{
    \(dq\&eight\(dq\&,                // alphabetically sorted number\-names
    \(dq\&five\(dq\&,
    \(dq\&four\(dq\&,
    \(dq\&nine\(dq\&,
    \(dq\&one\(dq\&,
    \(dq\&seven\(dq\&,
    \(dq\&six\(dq\&,
    \(dq\&ten\(dq\&,
    \(dq\&three\(dq\&,
    \(dq\&two\(dq\&
};

bool compFun(string const &left, string const &right)
{
    return left < right;
}

int main()
{
    string *ret = FBB::binary_search(words, words + 10, \(dq\&five\(dq\&);
    if (ret != words + 10)
        cout << \(dq\&five is at offset \(dq\& << (ret \- words) << endl;

    ret = FBB::binary_search(words, words + 10, \(dq\&grandpa\(dq\&);
    if (ret == words + 10)
        cout << \(dq\&grandpa is not the name of a number\en\(dq\&;

    ret = FBB::binary_search(words, words + 10, \(dq\&five\(dq\&, 
        [&](string const &element, string const &value)
        {
            return element < value;
        }
    );

    if (ret != words + 10)
        cout << \(dq\&five is at offset \(dq\& << (ret \- words) << endl;

    ret = FBB::binary_search(words, words + 10, \(dq\&grandpa\(dq\&, compFun); 
                                                   // or use: Comparator()
    if (ret == words + 10)
        cout << \(dq\&grandpa is not the name of a number\en\(dq\&;
}










.fi 

.PP 
and an example showing the use of different types:
.nf 
#include <iostream>
#include <string>
#include \(dq\&\&.\&./binarysearch\(dq\&

using namespace std;

struct Words
{
    string str;
    int value;
};

bool operator<(Words const &word, string const &str)
{
    return word\&.str < str;
}

bool operator<(string const &str, Words const &word)
{
    return str < word\&.str;
}

Words words[] = 
{
    { \(dq\&eight\(dq\&, 0 },                // alphabetically sorted number\-names
    { \(dq\&five\(dq\&, 0 },
    { \(dq\&four\(dq\&, 0 },
    { \(dq\&nine\(dq\&, 0 },
    { \(dq\&one\(dq\&, 0 },
    { \(dq\&seven\(dq\&, 0 },
    { \(dq\&six\(dq\&, 0 },
    { \(dq\&ten\(dq\&, 0 },
    { \(dq\&three\(dq\&, 0 },
    { \(dq\&two\(dq\&, 0 }
};

int main()
{
    auto ret = FBB::binary_search(words, words + 10, \(dq\&five\(dq\&, 
        [&](Words const &element, string const &value)
        {
            return element < value;
        }
    );

    cout << (ret != words + 10 ? \(dq\&found it\(dq\& : \(dq\&not present\(dq\&) << \(cq\&\en\(cq\&;
}










.fi 

.PP 
.SH "FILES"
\fIbobcat/binarysearch\fP \- defines the template functions
.PP 
.SH "SEE ALSO"
\fBbobcat\fP(7)
.PP 
.SH "BUGS"
None reported\&.
.PP 
.SH "BOBCAT PROJECT FILES"

.PP 
.IP o 
\fIhttps://fbb\-git\&.gitlab\&.io/bobcat/\fP: gitlab project page;
.IP o 
\fIbobcat_5\&.07\&.00\-x\&.dsc\fP: detached signature;
.IP o 
\fIbobcat_5\&.07\&.00\-x\&.tar\&.gz\fP: source archive;
.IP o 
\fIbobcat_5\&.07\&.00\-x_i386\&.changes\fP: change log;
.IP o 
\fIlibbobcat1_5\&.07\&.00\-x_*\&.deb\fP: debian package containing the
libraries;
.IP o 
\fIlibbobcat1\-dev_5\&.07\&.00\-x_*\&.deb\fP: debian package containing the
libraries, headers and manual pages;

.PP 
.SH "BOBCAT"
Bobcat is an acronym of `Brokken\(cq\&s Own Base Classes And Templates\(cq\&\&.
.PP 
.SH "COPYRIGHT"
This is free software, distributed under the terms of the 
GNU General Public License (GPL)\&.
.PP 
.SH "AUTHOR"
Frank B\&. Brokken (\fBf\&.b\&.brokken@rug\&.nl\fP)\&.
.PP