std::bsearch
来自 zh.cppreference.net
| 在头文件 <cstdlib>
|
||
void* bsearch( const void* key, const void* ptr, std::size_t count,
std::size_t size, /* c-compare-pred */* comp );
|
中定义 (1) | |
void* bsearch( const void* key, const void* ptr, std::size_t count,
std::size_t size, /* compare-pred */* comp );
|
(2) | |
void* bsearch( void* key, const void* ptr, std::size_t count,
std::size_t size, /* c-compare-pred */* comp );
|
(3) | (自 C++26) |
void* bsearch( void* key, const void* ptr, std::size_t count,
std::size_t size, /* compare-pred */* comp );
|
(4) | (自 C++26) |
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 指示为等于所搜索元素的元素，则函数返回哪一个元素的结果是未指定的。
参数
| key | - | 指向要搜索元素的指针 |
| ptr | - | 指向待检查数组的指针 |
| count | - | 数组中元素的数量 |
| size | - | 数组中每个元素的大小（以字节为单位） |
| comp | - | 比较函数，如果第一个参数小于第二个，则返回负整数值；如果第一个参数大于第二个，则返回正整数值；如果参数等价，则返回零。key作为第一个参数传递，数组中的一个元素作为第二个参数。比较函数的签名应等价于以下形式：
函数必须不修改传递给它的对象，并且在对相同对象（无论它们在数组中的位置如何）调用时必须返回一致的结果。 |
返回值
指向找到的元素的指针，如果未找到元素，则为空指针。
注解
尽管名称如此，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++20) |
|
C 文档 为 bsearch
| |