名前空間
変種

    bsearch, bsearch_s

    提供: cppreference.com
     
    C
     
    アルゴリズム
     
    <tbody> </tbody>
    ヘッダ <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) ptr の指す配列から key の指す要素と等しい要素を探します。 配列はそれぞれ size バイトの要素を count 個持ち、 key の指すオブジェクトに関して分割されていなければなりません。 つまり、キーオブジェクトより小さなすべての要素はキーオブジェクトと等しいすべての要素より前に現れなければならず、それらはキーオブジェクトより大きなすべての要素より前に現れなければなりません。 完全にソートされた配列はこれらの要件を満たします。 要素は comp の指す関数を使用して比較されます。 配列がキーに関して comp が使用するのと同じ基準に従ってあらかじめ昇順に分割されていない場合、動作は未定義です。
    2) (1) と同じですが、追加のコンテキスト引数 context が comp に渡され、以下のエラーが実行時に検出され、現在設定されている制約ハンドラ関数を呼びます。
    • count または size が RSIZE_MAX より大きい。
    • key、 ptr または comp がヌルポインタ (count がゼロでなければ)。
    すべての境界チェック付き関数と同様に、 bsearch_s は __STDC_LIB_EXT1__ が処理系によって定義されていて、 <stdlib.h> をインクルードする前にユーザが __STDC_WANT_LIB_EXT1__ を整数定数 1 に定義した場合にのみ、利用可能であることが保証されます。

    検索する要素と等しいと comp が示す要素が配列に複数含まれている場合、関数が結果としていずれの要素を返すかは未規定です。

    引数

    key - 検索する要素を指すポインタ
    ptr - 調べる配列を指すポインタ
    count - 配列の要素数
    size - 配列の各要素のバイト単位のサイズ
    comp - 第1引数が第2引数より小さい場合は負の整数値、第1引数が第2引数より大きい場合は正の整数値、第1引数と第2引数が同等な場合はゼロを返す比較関数。 key が第1引数として、配列の要素が第2引数として渡されます。

    比較関数のシグネチャは以下と同等であるべきです。

    int cmp(const void *a, const void *b);

    関数は渡されたオブジェクトを変更してはならず、同じオブジェクトに対してはその配列内の位置にかかわらず一貫した結果を返さなければなりません。

    ​

    context - comp に第3引数として渡される追加の情報 (照合シーケンスなど)

    戻り値

    1) *key と等しい配列内の要素を指すポインタ、またはそのような要素が見つからなかった場合はヌルポインタ。
    2) (1) と同じですが、実行時制約違反の場合もヌルポインタが返されます。

    ノート

    その名前にもかかわらず、 C も POSIX 標準もこの関数がバイナリサーチを用いて実装されることも、いかなる計算量の保証も、要求していません。

    他の境界チェック関数と異なり、 bsearch_s はサイズゼロの配列を実行時制約違反として扱わず、代わりに要素が見つからなかったことを示します (サイズゼロの配列を受理する他の関数は qsort_s です)。

    bsearch_s 以前、 bsearch のユーザは比較関数に追加のコンテキストを渡すためにしばしばグローバル変数を使用していました。

    例

    Run this code
    #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],