std::bsearch
来自cppreference.com
<tbody>
</tbody>
| 在标头 <cstdlib> 定义
|
||
void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* C 比较谓词 */* comp ); void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* 比较谓词 */* comp ); |
(1) | |
extern "C" using /* C 比较谓词 */ = int(const void*, const void*); extern "C++" using /* 比较谓词 */ = int(const void*, const void*); |
(2) | (仅用于阐述*) |
在 ptr 所指向的数组中寻找等于 key 所指向的元素的元素。数组含有 count 个 size 字节的元素，且必须相对于 key 所指向的对象划分，即所有比较小于它的元素必须先出现于比较等于它的元素，而比较等于它者必须先出现于所有比较大于该关键对象的元素。完全排序的数组满足这些要求。用 comp 所指的函数比较数组元素。
如果数组未以按照 comp 所用的相同原则相对于 key 升序划分，那么行为未定义。
如果数组含有多个元素会被 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 << "值 " << key;
if (p)
std::cout << "在位置 " << (p - arr.data())<< " 找到了";
else
std::cout << "没有找到";
}
}
输出：
在位置 3 找到了值 4
在位置 7 找到了值 8
没有找到值 9
参阅
| 对未指定类型的元素范围排序 (函数) | |
| 返回匹配特定键值的元素范围 (函数模板) | |
bsearch 的 C 文档
| |