std::bsearch

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

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

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

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

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

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

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

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

Параметры

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

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

Примечания

Несмотря на название, ни стандарт 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

Смотри также