【第1部】C言語（K＆R検証）編

００１６．配列内検索

ソース紹介

CPPファイルに記述

#include <iostream>
#include <cstdio>
using namespace std;

/*
v[0] <= v[n - 1]の中のxを探す
*/
int binsearch(int x, int v[], int n) {
    int low{0}, high{ n - 1 }, mid{0};
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid]) {
            high = mid - 1;
        }
        else if (x > v[mid]) {
            low = mid + 1;
        }
        else {
            //一致した
            return mid;
        }
    }
    return -1;
}

/*
binsearchのテスト
*/
int main()
{
    int arr[] = { 2,3,5,7,11,13,17,19 };
    int search[] = { 11, 5, 19 ,16, 23 };
    int j;
    for (int i = 0; i < sizeof(search) / sizeof(int); i++) {
        if ((j = binsearch(search[i], arr, sizeof(arr) / sizeof(int))) != -1) {
            cout << search[i] << "は" << j << "番目にみつかった" << endl;
        }
        else {
            cout << search[i] << "はみつからなかった"  << endl;
        }
    }
    return 0;
}

出力

11は4番目にみつかった
5は2番目にみつかった
19は7番目にみつかった
16はみつからなかった
23はみつからなかった

サンプル説明

　このサンプルは2分木のサンプルとなっています。
　ですので検索元となる配列arrは昇順に並んでいるのが条件となっています。

ソース紹介

　しかしC++で完全に記述する場合、setというコンテナが使えます。このコンテナは2分木を使ったデータの集合体です。また、検索するデータは、C++版の配列と言えるvectorが使えます。

CPPファイルに記述

#include <iostream>
#include <vector>
#include <set>
using namespace std;

/*
setのテスト
*/
int main()
{
    set<int> arr = { 17,19,2,3,13,5,7,11 };
    vector<int> search = { 11, 5, 19 ,16, 23 };
    for (auto v : search) {
        auto it = arr.find(v);
        if (it != arr.end()) {
            auto index = distance(arr.begin(), it);
            cout << v << "が" << index << "番目にみつかった" << endl;
        }
        else {
            cout << v << "はみつからなかった" << endl;
        }
    }
    return 0;
}

サンプル説明

　出力はbinsearch()関数版と同じです。
　setはデータ構造そのものが2分木になっています。ですから、上記のようにarrの初期化（データ設置）はばらばらでも構いません。初期化の段階で、内部で整列されます。
　最初から2分木なので、検索スピードもかなり速いです。
　またsearchのループは拡張for文を使ってます。ですので配列のインデックスも必要ありません。

K&Rでの記述

　元になったのは第3章:制御の流れに記述されています。Else-Ifの説明のところです。
　setやvectorのありがたみはこうしてbinsearch()関数を実際に書いてみないとわからないですね。