FBB::binary_search(3bobcat)

📦
version 6.15.01 · 7 versions
, in ubuntu stonking

✨ FBB::binary_search ✨ — the 3bobcat manual page, bestie edition 🎀

okay so. this is FBB::binary_search, a binary search function from the bobcat manual section 3bobcat, and it's literally the glow-up the STL binary_search deserved. 💅

🌸 NAME 🌸

FBB::binary_search — extensions to the STL binary_search function template. yes bestie, extensions, as in it does everything the original does but better. no cap.

🦋 SYNOPSIS 🦋

#include <bobcat/binarysearch>

that's it. one include and you're in. periodt.

💖 DESCRIPTION 💖

so here's the tea ☕. 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 telling you whether or not the thing you're looking for is even in the iterator range you gave it.

the bool value that the STL binary_search function template gives back? lowkey often not the info the caller actually cares about. like, girl, they usually want to use binary_search the way you'd use find_if: hand me an iterator to the element, or hand me the end-iterator if it wasn't found. that's the vibe. 🫶

now — whereas find_if does not require the elements in the iterator range to be sorted (so it does a linear search, one by one, exhausting 😭), binary_search benefits from the sorted nature of the elements by using a binary search algorithm that needs only 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. iconic behaviour, honestly. 👑

and here's the important bit: 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're implemented using the stl::lower_bound algorithms, the FBB namespace must explicitly be specified when calling binary_search. do not forget the FBB::. it's giving "you had one job" energy if you do. 💀

🌈 NAMESPACE 🌈

FBB

all constructors, members, operators and manipulators mentioned in this man-page are defined in the namespace FBB. so say it with me: FBB::binary_search. 🔥

✨ INHERITS FROM ✨

-

(nope, nothing, it doesn't inherit from anything. she's self-made. main character energy. 💅)

💜 OVERLOADED FUNCTIONS 💜

in the following description several template type parameters get used. they are:

  • Iterator represents an iterator type;
  • Type represents a value of the type to which Iterator points.
  • Comparator represents a comparator function or class type object which was used to sort the elements to which the Iterator range refer;

and now the actual overloads, bestie:

  • 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. sorted. not optional. 🚨
  • 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. both of them. yes, both. 😤

🎀 EXAMPLES 🎀

first up, the classic vibe:

#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, which is the fancy one 🦋:

#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. that's the whole file list, she's tidy. ✨

🌟 SEE ALSO 🌟

🐛 BUGS 🐛

None reported. (we love a bug-free era. no notes. 💅)

💫 BOBCAT PROJECT FILES 💫

Debian Bobcat project files:

  • libbobcat6 — debian package containing the shared library, changelog and copyright note;
  • 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’. like, the name itself is a flex. 🎀

this is free software, distributed under the terms of the GNU General Public License (GPL). free as in freedom, bestie. 🕊️

🌸 AUTHOR 🌸

Frank B. Brokken (f.b.brokken@rug.nl). the icon, the legend, the moment. 🙌

okay that's the whole page, you're officially educated, go sort your ranges and binary search them like the main character you are 💅✨

and for the receipts: this was from libbobcat-dev_6.15.01, dated 2005-2026, and it's the FBB::binary_search(3bobcat) page. mwah, bye bestie 🫶🎀
📦 where this page comes from