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

См. также