std:: bsearch

在由 ptr 指向的数组中查找与 key 所指向元素相等的元素。该数组包含 count 个元素，每个元素大小为 size 字节，且必须相对于 key 所指向的对象进行分区——即所有比较结果小于关键对象的元素必须出现在等于关键对象的元素之前，而这些又必须出现在所有比较结果大于关键对象的元素之前。完全排序的数组满足这些要求。使用 comp 所指向的函数对元素进行比较。

如果数组尚未按照与 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 << "值 " << key;
        if (p)
            std::cout << " 在位置 " << (p - arr.data()) << " 处找到\n";
        else
            std::cout << " 未找到\n";
    }
}

值 4 在位置 3 处找到
值 8 在位置 7 处找到
值 9 未找到

参见