◐ Shell
clean mode source ↗

std::bsearch - cppreference.com

提供: cppreference.com

<tbody> </tbody>

ヘッダ <cstdlib> で定義

void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /*compare-pred*/* comp ); void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /*c-compare-pred*/* comp );

 (1)

extern "C++" using /*compare-pred*/ = int(const void*, const void*); // exposition-only extern "C" using /*c-compare-pred*/ = int(const void*, const void*); // exposition-only

 (2)

ptr の指す配列から key の指す要素と等しい要素を探します。 配列はそれぞれ size バイトの要素を count 個持ち、 key の指すオブジェクトに関して分割されていなければなりません。 つまり、キーオブジェクトより小さなすべての要素はキーオブジェクトと等しいすべての要素より前に現れなければならず、それらはキーオブジェクトより大きなすべての要素より前に現れなければなりません。 完全にソートされた配列はこれらの要件を満たします。 要素は comp の指す関数を使用して比較されます。

配列がキーに関して comp が使用するのと同じ基準に従ってあらかじめ昇順に分割されていない場合、動作は未定義です。

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

引数

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

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

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

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

​

戻り値

見つかった要素を指すポインタ、または要素が見つからなかった場合はヌルポインタ。

ノート

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

引数 comp の型が異なるため (言語リンケージは型の一部です)、 C++ 標準ライブラリが提供する2つのオーバーロードは異なります。

例

#include <cstdlib>
#include <iostream>

int compare(const void *ap, const void *bp)
{
    const int *a = (int *) ap;
    const int *b = (int *) bp;
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
}

int main(int argc, char **argv)
{
    const int ARR_SIZE = 8;
    int arr[ARR_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8 };

    int key1 = 4;
    int *p1 = (int *) std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p1)
        std::cout << "value " << key1 << " found at position " << (p1 - arr) << '\n';
     else
        std::cout << "value " << key1 << " not found\n";

    int key2 = 9;
    int *p2 = (int *) std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p2)
        std::cout << "value " << key2 << " found at position " << (p2 - arr) << '\n';
     else
        std::cout << "value " << key2 << " not found\n";
}

出力: 

value 4 found at position 3
value 9 not found

関連項目