/usr/share/doc/libbobcat2-dev/man/binarysearch.3.html

<html><head>
<title>FBB::binary_search</title>
<link rev="made" href="mailto:Frank B. Brokken: f.b.brokken@rug.nl">
</head>
<body text="#27408B" bgcolor="#FFFAF0">
<hr>
<h1>FBB::binary_search</h1>
<h2>libbobcat1-dev_2.20.01-x.tar.gz</h2>
<h2>2005-2011</h2>

<html><head>
<link rev="made" href="mailto:Frank B. Brokken: f.b.brokken@rug.nl">
</head>
<body text="#27408B" bgcolor="#FFFAF0">
<hr>
<h1></h1>

<html><head>
<title>FBB::binary_search(3bobcat)</title>
<link rev="made" href="mailto:Frank B. Brokken: f.b.brokken@rug.nl">
</head>
<body text="#27408B" bgcolor="#FFFAF0">
<hr>
<h1>FBB::binary_search(3bobcat)</h1>
<h2>libbobcat1-dev_2.20.01-x.tar.gz Binary search function</h2>
<h2>2005-2011</h2>


<p>
<h2>NAME</h2>FBB::binary_search - Extensions to the STL binary_search function
template 
<p>
<h2>SYNOPSIS</h2>
    <strong>#include &lt;bobcat/binarysearch&gt;</strong><br>
<p>
<h2>DESCRIPTION</h2>
<p>
The <strong>FBB::binary_search</strong> function templates extend the STL <em>binary_search</em>
function template returning an iterator to the element found, instead of a
<strong>bool</strong> value informing the caller whether or not the searched for element is
present in a provided iterator range.
<p>
The <strong>bool</strong> value returned by the STL <em>binary_search</em> 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 <em>binary_search</em> in the way
<em>find_if</em> is used: returning an iterator to the found element or returning
the end-iterator if the element was not found. Whereas <em>find_if</em> does not
require the elements in the iterator range to be sorted, and thus will use a
linear search <em>binary_search</em> may use the sorted nature of the elements to
its advantage, using a binary search algorithm requiring <em>2 log N</em>
iterations to locate the searched for element rather than (on average) <em>N/2</em>
iterations. The <em>FBB::binary_search</em> algorithm uses this binary searching
process while at the same time allowing its use like <em>find_if</em>.  
<p>
Since the <em>FBB::binary_search</em> function templates use the same number and
types of parameters as the <em>stl::binary_search</em> function templates the
explicit use of the <em>FBB</em> namespace will often be required in situations
where both function templates are made available to the compiler.
<p>
<h2>NAMESPACE</h2>
    <strong>FBB</strong><br>
    All constructors, members, operators and manipulators, mentioned in this
man-page, are defined in the namespace <strong>FBB</strong>.
<p>
<h2>INHERITS FROM</h2>
    -
<p>
<h2>OVERLOADED FUNCTIONS</h2>
    In the following description several template type parameters are
used. They are:
    <ul>
    <li> <strong>Iterator</strong> represents an iterator type; 
    <li> <strong>Type</strong> represents a value of the type to which <em>Iterator</em>
points. 
    <li> <strong>Comparator</strong> represents a comparator function or class type object
which was used to sort the elements to which the <em>Iterator</em> range refer;
    </ul>
    <ul>
    <li> <strong>Iterator binary_search(Iterator begin, Iterator end, Type const
        &amp;value)</strong>:<br> 
       Using a binary search algorithm <em>value</em> 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 <em>end</em> is
returned. The elements in the range must have been sorted by the
<em>Type::operator&lt;()</em> function. 
    <li> <strong>Iterator binary_search(Iterator begin, Iterator end, Type const
        &amp;value, Comparator comparator)</strong>:<br> 
       Using a binary search algorithm <em>value</em> 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 <em>end</em> is
returned. The elements and the provided value are compared using
<em>comparator(*iterator, value)</em> calls, where <em>*iterator</em> refers to an
object in the provided iterator range. The elements in the range must have
been sorted by the <em>Comparator</em> function or function object.
    </ul>
<p>
<h2>EXAMPLES</h2>
        <pre>
#include &lt;iostream&gt;
#include &lt;string&gt;
#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 &amp;left, string const &amp;right) const;
};

inline bool Comparator::operator()(string const &amp;left, 
                                   string const &amp;right) const
{
    return left &lt; right;
}


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


int main()
{
    string *ret = binary_search(words, words + 10, "five");
    if (ret != words + 10)
        cout &lt;&lt; "five is at offset " &lt;&lt; (ret - words) &lt;&lt; endl;

    ret = binary_search(words, words + 10, "grandpa");
    if (ret == words + 10)
        cout &lt;&lt; "grandpa is not the name of a number\n";

    ret = binary_search(words, words + 10, "five", Comparator());
    if (ret != words + 10)
        cout &lt;&lt; "five is at offset " &lt;&lt; (ret - words) &lt;&lt; endl;

    ret = binary_search(words, words + 10, "grandpa", compFun); 
                                                   // or use: Comparator()
    if (ret == words + 10)
        cout &lt;&lt; "grandpa is not the name of a number\n";

    return 0;
}

</pre>

<p>
<h2>FILES</h2>
    <em>bobcat/binarysearch</em> - defines the template functions
<p>
<h2>SEE ALSO</h2>
    <strong>bobcat</strong>(7)
<p>
<h2>BUGS</h2>
    None reported.
<p>

<h2>DISTRIBUTION FILES</h2>
    <ul>
    <li> <em>bobcat_2.20.01-x.dsc</em>: detached signature;
    <li> <em>bobcat_2.20.01-x.tar.gz</em>: source archive;
    <li> <em>bobcat_2.20.01-x_i386.changes</em>: change log;
    <li> <em>libbobcat1_2.20.01-x_*.deb</em>: debian package holding the
            libraries;
    <li> <em>libbobcat1-dev_2.20.01-x_*.deb</em>: debian package holding the
            libraries, headers and manual pages;
    <li> <em>http://sourceforge.net/projects/bobcat</em>: public archive location;
    </ul>
<p>
<h2>BOBCAT</h2>
    Bobcat is an acronym of `Brokken's Own Base Classes And Templates'.
<p>
<h2>COPYRIGHT</h2>
    This is free software, distributed under the terms of the 
    GNU General Public License (GPL).
<p>
<h2>AUTHOR</h2>
    Frank B. Brokken (<strong>f.b.brokken@rug.nl</strong>).
<p>
libbobcat-dev 2.20.01-1 / usr / share / doc / libbobcat2-dev / man / binarysearch.3.html
