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) と同様であるが、追加の状態引数 context が comp に渡され、以下のエラーが実行時に検出され、現在インストールされている constraint handler 関数を呼び出す点が異なる：
  • count または size が RSIZE_MAX より大きい
  • key 、 ptr または comp がnullポインタである（ count がゼロの場合を除く）
すべての境界チェック付き関数と同様に、 bsearch_s （および対応する型汎用マクロ） (C23以降) は、実装によって __STDC_LIB_EXT1__ が定義され、かつユーザーが <stdlib.h> をインクルードする前に __STDC_WANT_LIB_EXT1__ を整数定数 1 に定義した場合にのみ利用可能であることが保証される。
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 - 比較関数。第1引数が第2引数より 小さい 場合は負の整数値、第1引数が第2引数より 大きい 場合は正の整数値、引数が等価の場合はゼロを返す。 key が第1引数として、配列の要素が第2引数として渡される。

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

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

この関数は渡されたオブジェクトを変更してはならず、配列内の位置に関わらず同じオブジェクトに対して呼び出された場合には一貫した結果を返さなければならない。

​

context - コンパレータの状態（照合順序など）。 comp に第3引数として渡される

戻り値

1) 配列内の要素へのポインタで、 * key と等しく比較されるもの、またはそのような要素が見つからなかった場合はヌルポインタ。
2) (1) と同様ですが、ランタイム制約違反の場合にもnullポインタが返される点が異なります。
3,4) (1) および (2) とそれぞれ同じですが、cv修飾が調整される点が異なります。

注記

名前にもかかわらず、C言語およびPOSIX標準は、この関数が二分探索を使用して実装されることや、複雑性に関する保証を一切要求していません。

他の境界チェック付き関数とは異なり、 bsearch_s はゼロサイズの配列を実行時制約違反として扱わず、代わりに要素が見つからなかったことを示します（ゼロサイズの配列を受け入れるもう1つの関数は 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関数

関連項目

(C11)
未指定の型の要素範囲をソートする
(関数)
C++ documentation for bsearch