directory search
Algorithms Algorithms(算法) bsearch bsearch_s qsort qsort_s Atomic operations Atomic operations library(原子操作库) ATOMIC_*_LOCK_FREE atomic_compare_exchange_strong atomic_compare_exchange_strong_explicit atomic_compare_exchange_weak atomic_compare_exchange_weak_explicit atomic_exchange atomic_exchange_explicit atomic_fetch_add atomic_fetch_add_explicit atomic_fetch_and atomic_fetch_and_explicit atomic_fetch_or atomic_fetch_or_explicit atomic_fetch_sub atomic_fetch_sub_explicit atomic_fetch_xor atomic_fetch_xor_explicit atomic_flag atomic_flag_clear atomic_flag_clear_explicit ATOMIC_FLAG_INIT atomic_flag_test_and_set atomic_flag_test_and_set_explicit atomic_init atomic_is_lock_free atomic_load atomic_load_explicit atomic_signal_fence atomic_store atomic_store_explicit atomic_thread_fence(线程围栏) ATOMIC_VAR_INIT kill_dependency memory_order(内存排序) C keywords auto(自动存储) break(跳出循环) C keywords(关键词) case char const(常量修饰符) continue default(预设运算式) do double(双精度浮点型) else enum(枚举类型) extern(全局变量) float(浮点数) for fortran goto(goto语句) if(if语句) inline(行内函式) int long(长整型) register(寄存器变量) restrict( restrict类型限定符) return short signed sizeof(sizeof运算符) static(静态变量) struct(结构体) switch(switch语句) typedef(typedef关键字) union(联合体) unsigned(无符号) void(空类型) volatile(volatile变量) while(while语句) _Alignas _Alignof _Atomic _Bool _Complex _Generic _Imaginary _Noreturn _Static_assert _Thread_local C language #define directive #elif directive #else directive #endif directive #error directive #if directive #ifdef directive #ifndef directive #include directive #line directive #pragma directive alignas(对齐指定符) Alternative operators and tokens(替代运算符和令牌) Analyzability Arithmetic operators Arithmetic types Array declaration(数组声明) Array initialization(阵列初始化) ASCII Chart Assignment operators(赋值运算符) types(atomic类型限定符) Basic concepts Bit fields(位域) break statement C language C Operator Precedence cast operator character constant(字符字面量) Comments(注释符) Comparison operators(比较运算符) compound literals(符合字面量) Conditional inclusion(条件包含) Conformance(一致性) const type qualifier(const 限定符) Constant expressions(常量表达) continue statement Declarations(声明) do-while loop Enumerations(枚举类型) Escape sequences(转义字符) Expressions(表达式) External and tentative definitions(外部和暂定的定义) File scope(文件范围) floating constant(浮点常量) for loop Function declarations(函数声明) Function definitions(函数声明) Functions Generic selection泛型选择 goto statement Identifier(标示符) if statement Implicit conversions(隐式转换) Increment/decrement operators(前置/后置操作符) Initialization(初始化) inline function specifier(内联函式) integer constant Lifetime(生命期) Logical operators(逻辑运算符) Lookup and name spaces Main function(主函式) Member access operators(会员接入运营商) Memory model Objects and alignment(字节对齐) Order of evaluation(评估顺序) Other operators Phases of translation(翻译阶段) Pointer declaration Preprocessor(预处理) restrict type qualifier(restrict类型限定符) return statement Scalar initialization(标量类型初始化) Scope(范围) sizeof operator(sizeof运算符) Statements(陈述) static assert declaration(静态断言声明) Static storage duration(静态存储周期) Storage-class specifiers(存储类说明符) string literals(字符串字面量) Struct and union initialization(结构体与联合体初始化) Struct declaration(结构体声明) switch statement Thread storage duration(线程存储时间) Type Type(类型) Typedef declaration(Typedef声明) Undefined behavior(未定义行为) Union declaration(联合体声明) Value categories(值类别) Variadic arguments(变长参数宏) volatile type qualifier(volatile 类型限定符) while loop _Alignof operator _Noreturn function specifier Date and time asctime(asctime函数) asctime_s clock CLOCKS_PER_SEC clock_t ctime(ctime函数) ctime_s Date and time utilities(日期和时间库) difftime(计算两个时间的间隔) gmtime gmtime_s localtime localtime_s mktime(将时间结构数据转换成经过的秒数的函数) strftime(格式化输出时间函数) time timespec timespec_get time_t tm wcsftime(格式化时间宽字符) Dynamic memory management aligned_alloc C memory management library(内存管理库) calloc free(释放动态分配空间的函数) malloc(动态分配内存空间的函数) realloc(重新分配内存空间的函数) Error handling abort_handler_s assert(断言) constraint_handler_t errno(错误报告) Error handling(错误处理) Error numbers(错误个数) ignore_handler_s set_constraint_handler_s static_assert File input/output clearerr(清除/复位) fclose feof ferror fflush(清空文件缓冲区) fgetc fgetpos fgets fgetwc fgetws File input/output fopen fopen_s fprintf fprintf_s fputc fputs fputwc fputws fread freopen freopen_s fscanf fscanf_s fseek fsetpos ftell fwide fwprintf fwprintf_s fwrite fwscanf fwscanf_s getc getchar gets gets_s getwchar perror printf printf_s putc putchar puts putwc putwchar remove rename rewind scanf scanf_s setbuf setvbuf snprintf sprintf sscanf sscanf_s swprintf swprintf_s swscanf swscanf_s tmpfile tmpfile_s tmpnam tmpnam_s ungetc ungetwc vfprintf vfprintf_s vfscanf vfscanf_s vfwprintf vfwprintf_s vfwscanf vfwscanf_s vprintf vprintf_s vscanf vscanf_s vsnprintf vsprintf vsscanf vsscanf_s vswprintf vswprintf_s vswscanf vswscanf_s vwprintf vwprintf_s vwscanf vwscanf_s wprintf wprintf_s wscanf wscanf_s Localization support lconv LC_ALL LC_COLLATE LC_CTYPE LC_MONETARY LC_NUMERIC LC_TIME localeconv Localization support setlocale Numerics abs acos acosf acosh acoshf acoshl acosl asin asinf asinh asinhf asinhl asinl atan atan2 atan2f atan2l atanf atanh atanhf atanhl atanl cabs cabsf cabsl cacos cacosf cacosh cacoshf cacoshl cacosl carg cargf cargl casin casinf casinh casinhf casinhl casinl catan catanf catanh catanhf catanhl catanl cbrt cbrtf cbrtl ccos ccosf ccosh ccoshf ccoshl ccosl ceil ceilf ceill cexp cexpf cexpl cimag cimagf cimagl clog clogf clogl CMPLX CMPLXF CMPLXL Common mathematical functions complex Complex number arithmetic conj conjf conjl copysign copysignf copysignl cos cosf cosh coshf coshl cosl cpow cpowf cpowl cproj cprojf cprojl creal crealf creall csin csinf csinh csinhf csinhl csinl csqrt csqrtf csqrtl ctan ctanf ctanh ctanhf ctanhl ctanl div double_t erf erfc erfcf erfcl erff erfl exp exp2 exp2f exp2l expf expl expm1 expm1f expm1l fabs fabsf fabsl fdim feclearexcept fegetenv fegetexceptflag fegetround feholdexcept feraiseexcept fesetenv fesetexceptflag fesetround fetestexcept feupdateenv FE_ALL_EXCEPT FE_DFL_ENV FE_DIVBYZERO FE_DOWNWARD FE_INEXACT FE_INVALID FE_OVERFLOW FE_TONEAREST FE_TOWARDZERO FE_UNDERFLOW FE_UPWARD Floating-point environment float_t floor floorf floorl fma fmaf fmal fmax fmaxf fmaxl fmin fminf fminl fmod fmodf fmodl fpclassify FP_INFINITE FP_NAN FP_NORMAL FP_SUBNORMAL FP_ZERO frexp frexpf frexpl HUGE_VAL HUGE_VALF HUGE_VALL hypot hypotf hypotl I ilogb ilogbf ilogbl imaginary imaxabs imaxdiv INFINITY isfinite isgreater isgreaterequal isinf isless islessequal islessgreater isnan isnormal isunordered labs ldexp ldexpf ldexpl ldiv lgamma lgammaf lgammal llabs lldiv llrint llrintf llrintl llround llroundf llroundl log log10 log10f log10l log1p log1pf log1pl log2 log2f log2l logb logbf logbl logf logl lrint lrintf lrintl lround lroundf lroundl MATH_ERREXCEPT math_errhandling MATH_ERRNO modf modff modfl nan NAN nanf nanl nearbyint nearbyintf nearbyintl nextafter nextafterf nextafterl nexttoward nexttowardf nexttowardl Numerics pow powf powl Pseudo-random number generation rand RAND_MAX remainder remainderf remainderl remquo remquof remquol rint rintf rintl round roundf roundl scalbln scalblnf scalblnl scalbn scalbnf scalbnl signbit sin sinf sinh sinhf sinhl sinl sqrt sqrtf sqrtl srand tan tanf tanh tanhf tanhl tanl tgamma tgammaf tgammal trunc truncf truncl Type-generic math _Complex_I _Imaginary_I Program support abort atexit at_quick_exit exit EXIT_FAILURE EXIT_SUCCESS getenv getenv_s jmp_buf longjmp Program support utilities quick_exit raise setjmp SIGABRT SIGFPE SIGILL SIGINT signal SIGSEGV SIGTERM sig_atomic_t SIG_DFL SIG_ERR SIG_IGN system _Exit Strings atof atoi atol atoll btowc c16rtomb c32rtomb char16_t char32_t isalnum isalpha isblank iscntrl isdigit isgraph islower isprint ispunct isspace isupper iswalnum iswalpha iswblank iswcntrl iswctype iswdigit iswgraph iswlower iswprint iswpunct iswspace iswupper iswxdigit isxdigit mblen mbrlen mbrtoc16 mbrtoc32 mbrtowc mbsinit mbsrtowcs mbsrtowcs_s mbstate_t mbstowcs mbstowcs_s mbtowc memchr memcmp memcpy memcpy_s memmove memmove_s memset memset_s Null-terminated byte strings Null-terminated multibyte strings Null-terminated wide strings strcat strcat_s strchr strcmp strcoll strcpy strcpy_s strcspn strerror strerrorlen_s strerror_s Strings library strlen strncat Thread support call_once cnd_broadcast cnd_destroy cnd_init cnd_signal cnd_timedwait cnd_wait mtx_destroy mtx_init mtx_lock mtx_plain mtx_recursive mtx_timed mtx_timedlock mtx_trylock mtx_unlock once_flag ONCE_FLAG_INIT thrd_busy thrd_create thrd_current thrd_detach thrd_equal thrd_error thrd_exit thrd_join thrd_nomem thrd_sleep thrd_success thrd_timedout thrd_yield Thread support library thread_local tss_create tss_delete TSS_DTOR_ITERATIONS tss_get tss_set Type support Boolean type support library Fixed width integer types FLT_EVAL_METHOD FLT_ROUNDS max_align_t NULL Numeric limits offsetof ptrdiff_t size_t Type support Variadic functions Variadic functions va_arg va_copy va_end va_list va_start
characters

在头文件<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并且在运行时检测到以下错误并调用当前安装的约束处理函数:

  • countsize大于RSIZE_MAX

  • keyptr或者comp是一个空指针(除非count是零)

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

If the array contains several elements that comp would indicate as equal to the element searched for, then it is unspecified which element the function will return as the result.

Parameters

-

指向要搜索的元素的指针

ptr

-

指向要检查的数组的指针

count

-

数组中元素的个数

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)

对一系列未指定类型的元素进行排序(函数)

| C++ documentation for bsearch |

Previous article: Next article: