FBB::binary_search(3bobcat)				      Binary search function				       FBB::binary_search(3bobcat)

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 ele-
       ment 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  com-
       piler.

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
";

	   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
";

	   return 0;
       }

FILES

       bobcat/binarysearch - defines the template functions

SEE ALSO

       bobcat(7)

BUGS

       None reported.

DISTRIBUTION FILES

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

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

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

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

       o      libbobcat1-dev_3.01.00-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).

libbobcat1-dev_3.01.00-x.tar.gz 				     2005-2012					       FBB::binary_search(3bobcat)