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

<!DOCTYPE html><html><head>
<meta charset="UTF-8">
<title>FBB::binary_search(3bobcat)</title>
<style type="text/css">
    figure {text-align: center;}
    img {vertical-align: center;}
    .XXfc {margin-left:auto;margin-right:auto;}
    .XXtc {text-align: center;}
    .XXtl {text-align: left;}
    .XXtr {text-align: right;}
    .XXvt {vertical-align: top;}
    .XXvb {vertical-align: bottom;}
</style>
<link rev="made" href="mailto:Frank B. Brokken: f.b.brokken@rug.nl">
</head>
<body text="#27408B" bgcolor="#FFFAF0">
<hr/>
<h1 id="title">FBB::binary_search(3bobcat)</h1>
<h2 id="author">Binary search function<br/>(libbobcat-dev_4.08.02-x.tar.gz)</h2>
<h2 id="date">2005-2017</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_4.08.02-x.dsc</em>: detached signature;
    <li> <em >bobcat_4.08.02-x.tar.gz</em>: source archive;
    <li> <em >bobcat_4.08.02-x_i386.changes</em>: change log;
    <li> <em >libbobcat1_4.08.02-x_*.deb</em>: debian package holding the
            libraries;
    <li> <em >libbobcat1-dev_4.08.02-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>
</body>
</html>
libbobcat-dev 4.08.02-2build1 / usr / share / doc / libbobcat4-dev / man / binarysearch.3.html
