std::bsearch
来自 cppreference.cn
| 定义于头文件 <cstdlib> |
||
| void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* c-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 指向的函数进行比较。
如果数组没有按照相对于 key 的升序方式划分（根据 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
| |
