bsearch、bsearch_s
来自 cppreference.com
定义于头文件 <stdlib.h> 中 |
||
(1) | ||
void* bsearch_s( const void *key, const void *ptr, rsize_t count, rsize_t size, int (*comp)(const void *, const void *, void *), |
(2) | (自 C11 起) |
(3) | (自 C23 起) | |
/*QVoid*/* bsearch_s( const void *key, /*QVoid*/ *ptr, rsize_t count, rsize_t size, int (*comp)(const void *, const void *, void *), |
(4) | (自 C23 起) |
1) 在由
ptr
指向的数组中查找等于由 key
指向的元素的元素。该数组包含 count
个大小为 size
字节的元素,并且必须根据 key
进行分区,即所有小于 key
的元素必须出现在所有等于 key
的元素之前,而这些元素必须出现在所有大于 key
的元素之前。完全排序的数组满足这些要求。元素使用由 comp
指向的函数进行比较。如果数组没有根据与 comp
使用的相同标准按升序顺序相对于 *key
进行分区,则行为未定义。2) 与 (1) 相同,除了将额外的状态参数
context
传递给 comp
以及在运行时检测到以下错误并调用当前安装的 约束处理程序 函数-
count
或size
大于 RSIZE_MAX -
key
、ptr
或comp
为空指针(除非count
为零)
-
- 与所有边界检查函数一样,
bsearch_s
(以及相应的类型通用宏)(自 C23 起) 仅在实现定义了 __STDC_LIB_EXT1__ 且用户在包含 <stdlib.h> 之前将 __STDC_WANT_LIB_EXT1__ 定义为整型常量 1 时才保证可用。
3,4) 分别与 (1) 和 (2) 等效的类型通用宏。令
T
为非限定对象类型(包括 void)。- 如果
ptr
的类型为 const T*,则返回类型为 const void*。 - 否则,如果
ptr
的类型为 T*,则返回类型为 void*。 - 否则,行为未定义。
- 如果
如果数组包含 comp
将指示为与要搜索的元素相等的多个元素,则该函数将返回哪个元素作为结果是不确定的。
实际函数 (1) 和 (2) 的直接使用已弃用。 |
(自 C23 起) |
内容 |
[编辑] 参数
key | - | 指向要搜索的元素的指针 |
ptr | - | 指向要检查的数组的指针 |
count | - | 数组中元素的数量 |
size | - | 数组中每个元素的大小(以字节为单位) |
comp | - | 比较函数,如果第一个参数小于第二个参数,则返回负整数值,如果第一个参数大于第二个参数,则返回正整数值,如果参数等效,则返回零。key 作为第一个参数传递,数组中的一个元素作为第二个参数传递。比较函数的签名应等效于以下内容 int cmp(const void *a, const void *b); 该函数不得修改传递给它的对象,并且对于相同的对象,无论它们在数组中的位置如何,都必须返回一致的结果。 |
context | - | 比较器的状态(例如,排序顺序),作为第三个参数传递给 comp |
[编辑] 返回值
1) 指向数组中与 *key 相等的元素的指针,如果未找到此类元素,则为 null 指针。
2) 与 (1) 相同,除了在运行时约束违反时也返回 null 指针。
3,4) 与 (1) 和 (2) 相同,除了 cv 限定符已调整。
[编辑] 说明
尽管有此名称,但 C 或 POSIX 标准均不要求此函数使用二分查找或提供任何复杂度保证。
与其他边界检查函数不同,bsearch_s
不会将大小为零的数组视为运行时约束违反,而是表示未找到元素(另一个接受大小为零的数组的函数是 qsort_s)。
在出现 bsearch_s
之前,bsearch
的用户通常使用全局变量来表示比较器的状态。
[编辑] 示例
运行此代码
#include <stdlib.h> #include <stdio.h> struct data { int nr; char const *value; } dat[] = { {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"} }; int data_cmp(void const *lhs, void const *rhs) { struct data const *const l = lhs; struct data const *const r = rhs; if (l->nr < r->nr) return -1; else if (l->nr > r->nr) return 1; else return 0; // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present) } int main(void) { struct data key = { .nr = 3 }; struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0], sizeof dat[0], data_cmp); if (res) { printf("No %d: %s\n", res->nr, res->value); } else { printf("No %d not found\n", key.nr); } }
输出
No 3: Hello
[编辑] 参考
- C17 标准(ISO/IEC 9899:2018)
- 7.22.5.1 bsearch 函数(p: 258)
- K.3.6.3.1 bsearch_s 函数(p: 441-442)
- C11 标准(ISO/IEC 9899:2011)
- 7.22.5.1 bsearch 函数(p: 355)
- K.3.6.3.1 bsearch_s 函数(p: 608-609)
- C99 标准(ISO/IEC 9899:1999)
- 7.20.5.1 bsearch 函数(p: 318-319)
- C89/C90 标准(ISO/IEC 9899:1990)
- 4.10.5.1 bsearch 函数
[编辑] 参见
(C11) |
对元素范围进行排序,元素类型未指定 (函数) |
C++ 文档 针对 bsearch
|