std::bsearch

Определено в заголовке <cstdlib>

Определено в заголовке `<cstdlib>`
void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* c-compare-pred / comp ); void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* compare-pred / comp );	(1)
extern "C" using /* c-compare-pred / = int(const void, const void); extern "C++" using / compare-pred / = int(const void, const void*);	(2)	(только для примера*)

void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, /* c-compare-pred */* comp );
void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, /* compare-pred */* comp );

(1)

extern "C" using /* c-compare-pred */ = int(const void*, const void*);
extern "C++" using /* compare-pred */ = int(const void*, const void*);

(2)

(только для примера*)

Находит элемент, равный элементу, на который указывает key, в массиве, на который указывает ptr. Массив содержит count элементов по size байт каждый и должен быть упорядочен относительно объекта, на который указывает key, то есть все элементы, которые сравниваются меньше, должны предшествовать всем элементам, которые сравниваются равными, а те, в свою очередь, должны предшествовать всем элементам, которые сравниваются больше ключа. Полностью отсортированный массив удовлетворяет этим требованиям. Элементы сравниваются с использованием функции, на которую указывает comp.

Поведение не определено, если массив не упорядочен по возрастанию относительно ключа согласно тому же критерию, что и comp.

Если массив содержит несколько элементов, которые comp указали бы как равные искомому элементу, то не определено, какой элемент функция вернёт в качестве результата.

Параметры

key	-	указатель на элемент для поиска
ptr	-	указатель на массив для проверки
count	-	количество элементов в массиве
size	-	размер каждого элемента в массиве в байтах
comp	-	функция сравнения, которая возвращает целое отрицательное значение, если первый аргумент меньше второго, целое положительное значение, если первый аргумент больше второго, и ноль, если аргументы эквивалентны.`key` передаётся в качестве первого аргумента, а элемент из массива - как второй. Подпись функции сравнения должна быть эквивалентна следующей: `int cmp(const void a, const void b);` Функция не должна изменять передаваемые ей объекты и должна возвращать согласованные результаты при вызове для одних и тех же объектов, независимо от их позиций в массиве.

Возвращаемое значение

Указатель на найденный элемент или нулевой указатель, если элемент не был найден.

Примечания

Несмотря на название, ни стандарты C, ни POSIX не требуют, чтобы эта функция реализовывалась с использованием двоичного поиска или обеспечивала какие-либо гарантии сложности.

Два перегруженных варианта, предоставляемые стандартной библиотекой C++, различаются, поскольку типы параметра comp различны (связь языка является частью его типа).

Пример

#include <array>
#include <cstdlib>
#include <iostream>
 
template<typename T>
int compare(const void *a, const void *b)
{
    const auto &arg1 = *(static_cast<const T*>(a));
    const auto &arg2 = *(static_cast<const T*>(b));
    const auto cmp = arg1 <=> arg2;
    return cmp < 0 ? -1
        :  cmp > 0 ? +1
        :  0;
}
 
int main()
{
    std::array arr{1, 2, 3, 4, 5, 6, 7, 8};
 
    for (const int key : {4, 8, 9})
    {
        const int* p = static_cast<int*>(
            std::bsearch(&key,
                arr.data(),
                arr.size(),
                sizeof(decltype(arr)::value_type),
                compare<int>));
 
        std::cout << "value " << key;
        if (p)
            std::cout << " found at position " << (p - arr.data()) << '\n'
        else
            std::cout << " not found\n";
    }
}

Вывод:

value 4 found at position 3
value 8 found at position 7
value 9 not found

См. также

qsort	сортирует диапазон элементов с неопределённым типом (функция)
equal_range	возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции)
Документация C для `bsearch`

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/bsearch