《その153》２分探索関数のプログラム例: C++，C++/CX に挑戦！

2017年11月27日

《その153》２分探索関数のプログラム例

　2 ﾌﾞﾝ
　２分探索関数のプログラム例

　新版明解C++中級編 p.122 にある汎用２分探索関数 binsearch のコードには、一部に誤植があると思うので、修正した binsearch関数と、それを利用するプログラムを以下に書きます。

　修正箇所は、binsearch関数の赤文字の部分です。
元のコードのままだと、pr が負になった状態で while文が実行される場合があり得ます。

　　comp < 0 で pl=0, pr=1 の状況のとき、
　　pc = (pl + pr) / 2 より pc = 0 ですから、
元のコードのままでは、次の
　　pr = pc - 1
の計算で、pr が負になります。そして、そのまま while文に戻ることになってしまいます。


// ------------------------------------
#include <string>
#include <iostream>

void* binsearch(
    const void* key,
    const void* base,
    size_t nmemb, size_t size,
    int(*compar)(const void*, const void*)
) {
    if (nmemb > 0) {
        const char* x
            = reinterpret_cast<const char*>(base);
        size_t pl = 0;          // 探索範囲先頭の添字
        size_t pr = nmemb - 1;  // 探索範囲末尾の添字
        size_t pc;              // 探索範囲中央の添字

        while (true) {
            pc = (pl + pr) / 2;
            int comp
                = compar(
                    key,
                    reinterpret_cast<const void*>(&x[pc * size])
                );
            if (comp == 0)      // 探索成功
                return const_cast<void*>(
                    reinterpret_cast<const void*>(&x[pc * size])
                    );
            else if (pl == pr)  // 探索範囲がなくなった
                break;
            else if (comp > 0)
                pl = pc + 1;    // 探索範囲を後半に絞り込む
            else if (pc > 0)    // comp < 0
                pr = pc - 1;    // 探索範囲を前半に絞り込む
            else                // comp < 0 && pc == 0
                break;
        }
    }
    return NULL;                // 探索失敗
}

int acmp(char* x, char* y) {            // 比較関数
    return strcmp(x, y);
}
int pcmp(char* x, char** y) {           // 比較関数
    return strcmp(x, *y);
}
int ncmp(int* x, int* y) {              // 比較関数
    return *x < *y ? -1 : *x > *y ? 1 : 0;
}
void existence(int n) { std::cout << n << "番目\n"; }
void non_existence() { std::cout << "該当なし\n"; }

int main() {
    char a[][5]
        = { "aaa", "aab", "abaa", "abb",
        "bab", "bab", "bab", "bbb" };
    const char* p[]
        = { "aaa", "aab", "abaa", "abb",
        "bab", "bab", "bab", "bbb" };
    int num[]
        = { 11, 21, 25, 31, 37, 44, 54,
        57, 65, 65, 65, 71, 88, 99 };

    // ------------------------------------
    std::cout << "◆";
    for (int i = 0; i < 8; i++)
        std::cout << a[i] << ' ';
    std::cout << '\n';

    char key1[10];
    std::cout << "  探索する文字列 : ";
    std::cin >> key1;
    std::cout << "  " << key1 << " → ";

    void* f = binsearch(
        key1,
        a,
        sizeof(a) / sizeof(a[0]),
        sizeof(a[0]),
        reinterpret_cast<int(*)(
            const void*,
            const void*
            )>(acmp)
    );

    if (f == 0) non_existence();
    else
        existence((char(*)[5])f - a + 1);

    // ------------------------------------
    std::cout << "\n◆";
    for (int i = 0; i < 8; i++)
        std::cout << p[i] << ' ';
    std::cout << '\n';

    char key2[10];
    std::cout << "  探索する文字列 : ";
    std::cin >> key2;
    std::cout << "  " << key2 << " → ";


    f = binsearch(
        key2,
        p,
        sizeof(p) / sizeof(p[0]),
        sizeof(p[0]),
        reinterpret_cast<int(*)(
            const void*,
            const void*
            )>(pcmp)
    );

    if (f == 0) non_existence();
    else
        existence((char**)f - p + 1);

    // ------------------------------------
    std::cout << "\n◆";
    for (int i = 0; i < 14; i++)
        std::cout << num[i] << ' ';
    std::cout << '\n';

    int key;
    std::cout << "  探索する整数値 : ";
    std::cin >> key;
    std::cout << "  " << key << " → ";

    f = binsearch(
        &key,
        num,
        sizeof(num) / sizeof(num[0]),
        sizeof(num[0]),
        reinterpret_cast<int(*)(
            const void*,
            const void*
            )>(ncmp)
    );

    if (f == 0) non_existence();
    else
        existence((int*)f - num + 1);
}