std::bsearch() 算法

C++98 起

// (1)
void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, cpp_compare_pred comp );

// (2)
void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, c_compare_pred comp );

仅用于说明的类型定义如下

extern "C++" using cpp_compare_pred = int(const void*, const void*);
extern "C" using c_compare_pred = int(const void*, const void*);

在 ptr 指向的数组中查找与 key 指向的元素相等的元素。

该数组包含 count 个元素，每个元素 size 字节，并且必须根据 key 指向的对象进行分区，即所有比较结果小于键对象的元素必须出现在所有比较结果等于键对象的元素之前，而这些元素又必须出现在所有比较结果大于键对象的元素之前。

完全排序的数组满足这些要求。元素使用 comp 指向的函数进行比较。

未定义行为

行为未定义

如果数组未根据 comp 使用的相同标准，按相对于 key 的升序进行分区。

如果数组包含多个 comp 会指示与要搜索的元素相等的元素，则函数将返回哪个元素作为结果是未指定的。

参数

键	指向要搜索的元素的指针。
ptr	指向要检查的数组的指针。
count	数组中的元素数量。
size	数组中每个元素的大小（字节）。
comp	比较函数，返回： 如果第一个参数小于第二个参数，则返回负整数值。 如果第一个参数大于第二个参数，则返回正整数值。 如果参数等效，则返回零。 比较函数的签名应等效于以下内容 int cmp(const void *a, const void *b); 函数不得修改传递给它的对象 当为相同的对象调用时，无论它们在数组中的位置如何，都必须返回一致的结果

返回值

指向找到的元素的指针，如果未找到元素则为 null 指针。

复杂度

未指定。

异常

(无)

备注

尽管有名称，但 C 和 POSIX 标准均不要求此函数使用二分搜索实现，也不做任何复杂度保证。

C++ 标准库提供的两个重载是不同的，因为参数 comp 的类型不同（语言链接是其类型的一部分）。

示例

Main.cpp

#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;
        (p) ? std::cout << " found at position " << (p - arr.data()) << '\n'
            : std::cout << " not found\n";
    }
}

输出

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