.TH "FBB::binary_search" "3bobcat" "2005\-2016" "libbobcat\-dev_4\&.04\&.00\-x\&.tar\&.gz" "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 template returning an iterator to the element found, 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 the found element or returning
the end\-iterator if the element was not found\&. Whereas \fIfind_if\fP does not
require the elements in the iterator range to be sorted, and thus will use a
linear search \fIbinary_search\fP may use the sorted nature of the elements to
its advantage, 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 its use 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 the
explicit use of the \fIFBB\fP namespace will often be required in situations
where both function templates are made available to the compiler\&.
.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;
.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::operator<()\fP function\&. 
.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\&.

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

using namespace std;
using namespace FBB;

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\&
};

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, \(dq\&five\(dq\&);
    if (ret != words + 10)
        cout << \(dq\&five is at offset \(dq\& << (ret \- words) << endl;

    ret = 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 = binary_search(words, words + 10, \(dq\&five\(dq\&, Comparator());
    if (ret != words + 10)
        cout << \(dq\&five is at offset \(dq\& << (ret \- words) << endl;

    ret = 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\&;

    return 0;
}


.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 "DISTRIBUTION FILES"
.IP o 
\fIbobcat_4\&.04\&.00\-x\&.dsc\fP: detached signature;
.IP o 
\fIbobcat_4\&.04\&.00\-x\&.tar\&.gz\fP: source archive;
.IP o 
\fIbobcat_4\&.04\&.00\-x_i386\&.changes\fP: change log;
.IP o 
\fIlibbobcat1_4\&.04\&.00\-x_*\&.deb\fP: debian package holding the
libraries;
.IP o 
\fIlibbobcat1\-dev_4\&.04\&.00\-x_*\&.deb\fP: debian package holding the
libraries, headers and manual pages;
.IP o 
\fIhttp://sourceforge\&.net/projects/bobcat\fP: public archive location;

.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