Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_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 进行分区，即所有比较小于的元素必须出现在比较等于的元素之前，而这些元素又必须出现在所有比较大于关键对象的元素之前。完全排序的数组满足这些要求。使用 comp 指向的函数比较元素。如果数组未按照 comp 使用的相同准则相对于 *key 以升序预先分区，则行为未定义。
2) 与 (1) 相同，区别在于向 comp 传递了额外的状态参数 context ，且在运行时检测到以下错误时会调用当前安装的 约束处理函数 ：
  • 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) 的做法已被弃用。

(since 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); // 可能的快捷方式
    // return l->nr - r->nr; // 错误的快捷方式（如果存在 INT_MIN 会失败）
}
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 函数 (页码: 258)
  • K.3.6.3.1 bsearch_s 函数 (页码: 441-442)
  • C11 标准 (ISO/IEC 9899:2011):
  • 7.22.5.1 bsearch 函数 (第 355 页)
  • K.3.6.3.1 bsearch_s 函数 (第 608-609 页)
  • C99标准（ISO/IEC 9899:1999）：
  • 7.20.5.1 bsearch函数（页码：318-319）
  • C89/C90 标准 (ISO/IEC 9899:1990):
  • 4.10.5.1 bsearch 函数

参见

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