線形探索 search

線形探索の終了判定テクニック

線形探索の終了判定テクニック
Feb. 2, 2020, 1:52 p.m.

目次

配列の最後の要素に探索対象を上書きし「番兵」をおき、必ず対象が見つかるようにする.
これによりループ内から探索対象との比較の条件分岐を1つ減らすことができる.

アルゴリズム

  1. 配列の末尾が対象と等しければ真を返して終了
  2. 配列の末尾の要素を後で復元するために一時退避
  3. 配列の末尾を対象で上書きする
  4. 探索インデックスを0で初期化
  5. 探索インデックスにおける配列の要素が対象と異なる間次に進める
  6. 配列の末尾の要素を一時退避から復元する
  7. 探索が番兵で終了した場合は偽、それより前で終了した場合は真を返す

コード

1
2
3
4
5
6
7
8
9
bool search(vector<int> v, int target) {
    if (v[v.size() - 1] == target) return true; // 1
    int stash = v[v.size() - 1]; // 2
    v[v.size() - 1] = target; // 3
    int i = 0; // 4
    while (v[i] != target) i++; // 5
    v[v.size() - 1] = stash; // 6
    return i != v.size() - 1; // 7
}