NAME

       FBB::binary_search - Extensions to the STL binary_search function template

SYNOPSIS

       #include <bobcat/binarysearch>

DESCRIPTION

       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.

NAMESPACE

       FBB
       All constructors, members, operators and manipulators, mentioned  in  this  man-page,  are
       defined in the namespace FBB.

INHERITS FROM

       -

OVERLOADED FUNCTIONS

       In the following description several template type parameters are used. They are:

       o      Iterator represents an iterator type;

       o      Type represents a value of the type to which Iterator points.

       o      Comparator  represents a comparator function or class type object which was used to
              sort the elements to which the Iterator range refer;

       o      Iterator binary_search(Iterator begin, Iterator end, Type const &value):
              Using a binary search algorithm value 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 end is returned. The elements in  the
              range must have been sorted by the Type::operator<() function.

       o      Iterator  binary_search(Iterator begin, Iterator end, Type const &value, Comparator
              comparator):
              Using a binary search algorithm value 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 end is returned. The elements and the
              provided  value  are  compared  using  comparator(*iterator,  value)  calls,  where
              *iterator refers to an object in the provided iterator range. The elements  in  the
              range must have been sorted by the Comparator function or function object.

EXAMPLES

       #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;
       }

FILES

       bobcat/binarysearch - defines the template functions

SEE ALSO

       bobcat(7)

BUGS

       None reported.

DISTRIBUTION FILES

       o      bobcat_3.19.01-x.dsc: detached signature;

       o      bobcat_3.19.01-x.tar.gz: source archive;

       o      bobcat_3.19.01-x_i386.changes: change log;

       o      libbobcat1_3.19.01-x_*.deb: debian package holding the libraries;

       o      libbobcat1-dev_3.19.01-x_*.deb:  debian  package holding the libraries, headers and
              manual pages;

       o      http://sourceforge.net/projects/bobcat: public archive location;

BOBCAT

       Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.

COPYRIGHT

       This is free software, distributed under the terms  of  the  GNU  General  Public  License
       (GPL).

AUTHOR

       Frank B. Brokken (f.b.brokken@rug.nl).