---
name: "binarysearch"
section: "3bobcat"
platform: "linux"
package: "libbobcat-dev"
version: "6.07.01-2"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/binarysearch"
---

# binarysearch(3bobcat)

Extensions to the STL binary\_search function template

## 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 templates by returning an iterator to the found element, 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 an 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 therefore uses a linear search, *binary\_search* benefits from the sorted nature of the elements 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 it to be used 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 and because they are implemented using the *stl::lower\_bound* algorithms the *FBB* namespace must explicitly be specified when calling *binary\_search*.

## 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’s 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.

-

  The *comparator* function is called with two arguments. The first argument refers to an element in the *begin..end* range, the second argument refers to *value*.

-

  Usually the types of these arguments are identical, but they may differ. Assuming that *Iterator* refers to elements of a type *Data*, then comparison operators *bool operator\<(Data const &lhs, Type const &rhs)* and *bool operator\<(Type const &rhs, Data const &lhs)* must both be available.

## EXAMPLES

```
#include <iostream>
#include <string>
#include <bobcat/binarysearch>
using namespace std;
string words[] =
{
    "eight",                // alphabetically sorted number-names
    "five",
    "four",
    "nine",
    "one",
    "seven",
    "six",
    "ten",
    "three",
    "two"
};
bool compFun(string const &left, string const &right)
{
    return left < right;
}
int main()
{
    string *ret = FBB::binary_search(words, words + 10, "five");
    if (ret != words + 10)
        cout << "five is at offset " << (ret - words) << endl;
    ret = FBB::binary_search(words, words + 10, "grandpa");
    if (ret == words + 10)
        cout << "grandpa is not the name of a number\n";
    ret = FBB::binary_search(words, words + 10, "five",
        [&](string const &element, string const &value)
        {
            return element < value;
        }
    );
    if (ret != words + 10)
        cout << "five is at offset " << (ret - words) << endl;
    ret = FBB::binary_search(words, words + 10, "grandpa", compFun);
                                                   // or use: Comparator()
    if (ret == words + 10)
        cout << "grandpa is not the name of a number\n";
}
```

and an example showing the use of different types:

```
#include <iostream>
#include <string>
#include <bobcat/binarysearch>
using namespace std;
struct Words
{
    string str;
    int value;
};
bool operator<(Words const &word, string const &str)
{
    return word.str < str;
}
bool operator<(string const &str, Words const &word)
{
    return str < word.str;
}
Words words[] =
{
    { "eight", 0 },                // alphabetically sorted number-names
    { "five", 0 },
    { "four", 0 },
    { "nine", 0 },
    { "one", 0 },
    { "seven", 0 },
    { "six", 0 },
    { "ten", 0 },
    { "three", 0 },
    { "two", 0 }
};
int main()
{
    auto ret = FBB::binary_search(words, words + 10, "five",
        [&](Words const &element, string const &value)
        {
            return element < value;
        }
    );
    cout << (ret != words + 10 ? "found it" : "not present") << ’\n’;
}
```

## FILES

*bobcat/binarysearch* - defines the template functions

## SEE ALSO

[**bobcat**(7)](/bobcat/7.md)

## BUGS

None reported.

## BOBCAT PROJECT FILES

- o

  *https://fbb-git.gitlab.io/bobcat/*: gitlab project page;

Debian Bobcat project files:

- o

  *libbobcat6*: debian package containing the shared library, changelog and copyright note;

- o

  *libbobcat-dev*: debian package containing the static library, headers, manual pages, and developer info;

## 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**).