非常教程

C参考手册

算法 | Algorithms

bsearch

在头文件<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以来)

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

2)与(1)相同,只是context传递附加的上下文参数,comp并且在运行时检测到以下错误并调用当前安装的约束处理函数:

  • count or size is greater than RSIZE_MAX
  • key, ptr or comp is a null pointer (unless count is zero)

与所有边界检查的函数一样,bsearch_s只有__STDC_LIB_EXT1__在实现定义并且用户在包含之前定义__STDC_WANT_LIB_EXT1__为整数常量时1才能保证可用stdlib.h

如果该数组包含多个元素,这些元素comp将指示与搜索的元素相同,则未指定函数将作为结果返回的元素。

参数

-

指向要搜索的元素的指针

ptr

-

指向要检查的数组的指针

size

-

数组中元素的个数

size

-

数组中每个元素的大小(以字节为单位)

comp

-

比较函数,如果第一个参数小于第二个参数,则返回负整数值;如果第一个参数大于第二个参数,则返回正整数值;如果参数相等,则返回零。键作为第一个参数传递,数组中的元素作为第二个参数。比较函数的签名应该等同于以下内容:int cmp(const void * a,const void * b); 该函数不得修改传递给它的对象,并且在调用相同对象时必须返回一致的结果,而不管它们在数组中的位置。

context

-

附加信息(例如,整理顺序),作为第三个参数传递给comp

返回值

1)指向数组中等于*key或等于的元素的指针,或者如果没有找到该元素,则返回空指针。

2)与(1)相同,只是空指针在运行时约束违规时也返回。

笔记

尽管名称不同,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

参考

  • 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 ++文档 |

算法 | Algorithms相关

C

C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。