サーチアルゴリズムおさらい

引き続きサーチアルゴリズムのおさらい + C++へ慣れる為の作業

# リニアサーチ O (N)
C++標準ライブラリのfind()はこれを使ってるらしい。

void linear_search(int s, vector<int> v) {
    cout << "search " << s << " ... ";
    int i;
    for (i = 0; i < v.size(); i++) {
        if (s == v.at(i)) {
            cout << "FOUND at " << i + 1 << endl;
            return;
        }
    }
    cout << "not FOUND" << endl;
}

# 番兵利用リニアサーチ O (N)
添字チェックを行わない。

void sentinel_search(int s, vector<int> v) {

    cout << "search " << s << " ... ";

    int i = 0, t = v[N - 1];
    v[N - 1] = s;

    while (v[i] != s)
        i++;

    if (i < N - 1) {
        cout << "FOUND at " << i + 1 << endl;
        return;
    }

    if (s == t) {
        cout << "FOUND at " << N << endl;
        return;
    }

    cout << "not FOUND" << endl;
}

# バイナリサーチ O (log N)

void binary_search(int t, int *array) {
    cout << "search " << t << endl;
    int l = 0, r = N-1, m;
    while (l <= r) {
        m = (l + r) / 2;
        if (array[m] == t) {
            cout << t << " found at " << m + 1 << endl;
            return;
        }
        if (array[m] < t) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << "not found" << endl;
}

# バイナリサーチ改良版 O (log N)
同じ値が配列内で複数存在する場合に先頭の値を返す。

void binary_search(int t, int *array) {
    cout << "search " << t << endl;
    int l = 0, r = N-1, m;
    while (l < r) {
        m = (l + r) / 2;
        if (array[m] < t) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if (array[l] == t) {
        cout << t << " found at " << l + 1 << endl;
        return;
    }
    cout << "not found" << endl;
}

# 自己組織化探索
見つかった値を1つ前へ移動する。

void organization_search(int t, int *array) {
    int i, tmp;
    while (array[i] != t && i < N)
        i++;
    if (i < N && 0 < N) {
        tmp = array[i];
        array[i] = array[i - 1];
        array[i - 1] = tmp;
    }
}

まだvector::iteratorの使い方に慣れてない...