bsearch, bsearch_s

 

C

コンパイラサポート

言語

ヘッダー

型サポート

プログラムユーティリティ

可変長引数関数のサポート

エラーハンドリング

動的メモリ管理

文字列ライブラリ

アルゴリズム

数値

日付と時刻のユーティリティ

入出力サポート

ローカライゼーションサポート

並行処理サポート (C11)

技術仕様

シンボルインデックス

 

アルゴリズム

qsortqsort_s (C11)

bsearchbsearch_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 に対してパーティショニングされている必要があります。つまり、key よりも小さい要素はすべて key と等しい要素の前に、key と等しい要素はすべて key よりも大きい要素の前に配置されている必要があります。完全にソートされた配列はこれらの要件を満たします。要素の比較には comp が指す関数が使用されます。配列が comp と同じ基準で昇順に *key に対してパーティショニングされていない場合、動作は未定義です。

2) (1) と同じですが、追加の状態引数 context が comp に渡され、以下のエラーが実行時に検出されて、現在インストールされている 制約ハンドラ関数が呼び出されます。

• count または size が RSIZE_MAX より大きい
• key、ptr、または comp がヌルポインタである（count がゼロの場合は除く）

すべての境界チェック関数と同様に、bsearch_s （および対応する型汎用マクロ）は、実装によって __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引数より *小さい* 場合は負の整数値、 *大きい* 場合は正の整数値、両者が *等しい* 場合はゼロを返します。key が第1引数として、配列の要素が第2引数として渡されます。 比較関数のシグネチャは、以下と同等でなければならない。  int cmp(const void *a, const void *b); この関数は、渡されたオブジェクトを変更してはならず、同じオブジェクトに対して呼び出された場合、配列内の位置に関係なく一貫した結果を返さなければなりません。 ​
コンテキスト	-	コンパイラの状態（例: コリェーティングシーケンス）で、comp に第3引数として渡されます。

戻り値

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); // 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 The bsearch function (p: 258)

• K.3.6.3.1 The bsearch_s function (p: 441-442)

• C11標準 (ISO/IEC 9899:2011)

• 7.22.5.1 The bsearch function (p: 355)

• K.3.6.3.1 The bsearch_s function (p: 608-609)

• C99標準 (ISO/IEC 9899:1999)

• 7.20.5.1 The bsearch function (p: 318-319)

• C89/C90標準 (ISO/IEC 9899:1990)

• 4.10.5.1 The bsearch function

関連項目

qsortqsort_s (C11)	型が指定されていない要素の範囲をソートする (関数)
C++ ドキュメント for bsearch