命名空间
变体
操作

std::bsearch

来自 cppreference.com
< cpp‎ | algorithm
 
 
算法库
受限算法和范围上的算法 (C++20)
受限算法,例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分搜索操作
(在分区范围内)
集合操作(在排序范围内)
合并操作(在排序范围内)
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比较操作
排列操作
C 库
bsearch
数值操作
未初始化内存上的操作
 
在头文件 <cstdlib> 中定义
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 );
(1)
extern "C" using /* c-compare-pred */ = int(const void*, const void*);
extern "C++" using /* compare-pred */ = int(const void*, const void*);
(2) (仅作说明*)

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

如果数组尚未根据与 comp 使用相同的标准按升序对键进行分区,则行为未定义。

如果数组包含多个 comp 将指示为等于要搜索的元素的元素,则该函数将返回哪个元素作为结果是不确定的。

内容

[编辑] 参数

key - 指向要搜索的元素的指针
ptr - 指向要检查的数组的指针
count - 数组中的元素数量
size - 数组中每个元素的大小(以字节为单位)
comp - 比较函数,如果第一个参数 小于 第二个参数,则返回负整数;如果第一个参数 大于 第二个参数,则返回正整数;如果参数相等,则返回零。 key 作为第一个参数传递,数组中的元素作为第二个参数传递。

比较函数的签名应等效于以下内容

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

该函数不得修改传递给它的对象,并且在针对同一对象调用时必须返回一致的结果,无论它们在数组中的位置如何。

[编辑] 返回值

指向找到的元素的指针,如果未找到元素,则返回空指针。

[编辑] 备注

尽管有这个名字,但 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

[编辑] 另请参见

对范围内的元素进行排序,元素类型未指定
(函数) [编辑]
返回与特定键匹配的元素范围
(函数模板) [编辑]
C 文档 适用于 bsearch