bsearch, bsearch_s

 

C

编译器支持

语言

头文件

类型支持

程序工具

可变参数函数支持

错误处理

动态内存管理

字符串库

算法

数值

日期和时间工具

输入/输出支持

本地化支持

并发支持 (C11)

技术规范

符号索引

 

算法

qsortqsort_s (C11)

bsearchbsearch_s (C11)

 

定义于头文件 <stdlib.h>
void* bsearch( const void *key, const void *ptr, size_t count, size_t size,                int (*comp)(const void*, const void*) );	(1)
void* bsearch_s( const void *key, const void *ptr, rsize_t count, rsize_t size,                  int (*comp)(const void *, const void *, void *),                  void *context );	(2)	(始于 C11)
/*QVoid*/* bsearch( const void *key, /*QVoid*/ *ptr, size_t count, size_t size,                     int (*comp)(const void*, const void*) );	(3)	(始于 C23)
/*QVoid*/* bsearch_s( const void *key, /*QVoid*/ *ptr, rsize_t count, rsize_t size,                       int (*comp)(const void *, const void *, void *),                       void *context );	(4)	(始于 C23)

1) 查找一个元素，该元素等于 ptr 指向的数组中 key 指向的元素。该数组包含 count 个大小为 size 字节的元素，并且必须相对于 key 进行分区，也就是说，所有比较结果小于 key 的元素必须出现在所有比较结果等于 key 的元素之前，而这些元素必须出现在所有比较结果大于键对象的元素之前。完全排序的数组满足这些要求。元素使用 comp 指向的函数进行比较。如果数组尚未根据 comp 使用的相同标准，以升序相对于 *key 进行分区，则行为未定义。

2) 与 (1) 相同，但附加的状态参数 context 传递给 comp，并且在运行时检测到以下错误并调用当前安装的约束处理函数

• count 或 size 大于 RSIZE_MAX
• key、ptr 或 comp 是空指针（除非 count 为零）

与所有边界检查函数一样，只有当实现定义了 __STDC_LIB_EXT1__ 并且用户在包含 <stdlib.h> 之前将 __STDC_WANT_LIB_EXT1__ 定义为整数常量 1 时，才能保证 bsearch_s （以及相应的类型通用宏）(自 C23 起) 可用。

3,4) 分别等效于 (1) 和 (2) 的类型通用宏。令 T 为非限定对象类型（包括 void）。

• 如果 ptr 的类型为 const T*，则返回类型为 const void*。
• 否则，如果 ptr 的类型为 T*，则返回类型为 void*。
• 否则，行为未定义。

如果抑制每个通用函数的宏定义以访问实际函数（例如，(bsearch)、(bsearch_s) 或使用函数指针），则实际函数声明 (1) 或 (2) 变为可见。

如果数组包含多个 comp 指示为等于搜索元素的元素，则未指定函数将返回哪个元素作为结果。

直接使用实际函数 (1) 和 (2) 已弃用。

(始于 C23)

参数

key	-	指向要搜索的元素的指针
ptr	-	指向要检查的数组的指针
count	-	数组中元素的数量
size	-	数组中每个元素的大小（以字节为单位）
comp	-	比较函数，如果第一个参数小于第二个参数，则返回负整数值；如果第一个参数大于第二个参数，则返回正整数值；如果参数相等，则返回零。 key 作为第一个参数传递，数组中的一个元素作为第二个参数传递。 比较函数的签名应等效于以下内容  int cmp(const void *a, const void *b); 该函数不得修改传递给它的对象，并且在为相同对象调用时，无论它们在数组中的位置如何，都必须返回一致的结果。 ​
context	-	比较器的状态（例如，排序规则），作为第三个参数传递给 comp

返回值

1) 指向数组中与 *key 相等的元素的指针；如果未找到此类元素，则为空指针。

2) 与 (1) 相同，不同之处在于在运行时约束冲突时也返回空指针。

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 函数

参见

qsortqsort_s (C11)	对未指定类型的元素范围进行排序 (函数)
bsearch 的 C++ 文档