std::bsearch

< cpp‎ | algorithm
 
C++
 
算法库
有制约算法及范围上的算法 (C++20)
有制约算法： std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
(C++11)
二分搜索操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

排列
数值运算
C 库
bsearch
 
定义于头文件 <cstdlib>
void* bsearch( const void* key, const void* ptr, std::size_t count,

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

               std::size_t size, /*c-compare-pred*/* comp );
 (1)
extern "C++" using /*compare-pred*/ = int(const void*, const void*); // 仅为说明
extern "C" using /*c-compare-pred*/ = int(const void*, const void*); // 仅为说明
 (2)

在 ptr 所指向的数组中寻找等于 key 所指向的元素的元素。数组含有 count 个 size 字节的元素，且必须相对于 key 所指向的对象划分，即所有比较小于它的元素必须先出现于比较等于它的元素，而比较等于它者必须先出现于所有比较大于该关键对象的元素。完全排序的数组满足这些要求。用 comp 所指的函数比较数组元素。

若数组未以按照 comp 所用同样原则，相对于 key 升序划分，则行为未定义。

若数组含有数个 comp 会指示等于被搜索元素的元素，则函数返回哪个元素是未指定的。

参数

key - 指向要搜索的元素的指针
ptr - 指向要检验的数组的指针
count - 数组中元素的数量
size - 数组中每个元素的大小，以字节表示
comp - 比较函数。若首个参数小于第二个，则返回负整数值，若首个参数大于第二个，则返回正整数值，若两参数等价，则返回零。作为首参数传递 key ，作为第二参数传递来自数组的元素。

比较函数的签名应等价于如下形式：

 int cmp(const void *a, const void *b);

该函数必须不修改传递给它的对象，而且在调用比较相同对象时必须返回一致的结果，无关乎它们在数组中的位置。

​

返回值

指向找到的元素的指针，或若找不到元素则为空指针。

注意

无关乎名称， C 或 POSIX 标准都不要求此函数用二分查找实现，或进行任何复杂度保证。

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

示例

运行此代码
#include <cstdlib>
#include <iostream>
 
int compare(const void *ap, const void *bp)
{
    auto a = static_cast<const int *>(ap);
    auto b = static_cast<const int *>(bp);
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
}
 
int main(int argc, char **argv)
{
    const int ARR_SIZE = 8;
    int arr[ARR_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
    int key1 = 4;
    int *p1 = (int *) std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p1)
        std::cout << "value " << key1 << " found at position " << (p1 - arr) << '\n';
     else
        std::cout << "value " << key1 << " not found\n";
 
    int key2 = 9;
    int *p2 = (int *) std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p2)
        std::cout << "value " << key2 << " found at position " << (p2 - arr) << '\n';
     else
        std::cout << "value " << key2 << " not found\n";
}

输出： 

value 4 found at position 3
value 9 not found

参阅

 对未指定类型的元素的一个范围进行排序
(函数)
返回匹配特定键值的元素范围
(函数模板)