番兵を用いたちょっと効率的な線形探索 - プログラミング原人の進化論

アルゴリズムとデータ構造について勉強していて、探索アルゴリズムについて学んだのでメモを残しておきます。今回は線形探索です。
実装しながら簡単な説明をして、それから問題を解きます。

目標

線形探索を実装できるようになる。

線形探索

多数の要素が並んだ配列に対する探索を考えます。線形探索とは、配列の先頭から調べていき、目当ての要素を発見したら探索を終了する、という非常に単純なアルゴリズムです。
探索の方法を考えろと言われた初心者はまず最初にこれを思いつくのではないでしょうか。しかし効率は非常に悪そうですね。

まず何も考えずに実装してみる

とりあえず実装してみましょう。与えられたキーが、配列に含まれるか否かを判別する関数を作ります。

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  for (int i = 0; i < n; i++) {
    if (A[i] == key) return true;
  }
  return false;
}

番兵を用いた実装

少し工夫することで、より効率的な探索ができます。具体的には、番兵と呼ばれるものを導入します。どういうものかというと、配列の末尾の次に、探したいキーと同じ値を持った要素を入れておきます。
これを用いると、上のようにループの停止条件を入れる必要がありません。なぜなら、キーと一致するものがなくても一番後ろの番兵で必ず停止するからです。上の関数を書き換えると、

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  int i = 0;
  A[n] = key;  // 番兵の設置
  while (A[i] != key) i++;
  return i != n;
}

iがnと一致するなら（番兵にたどり着いたら）falseを返し、そうでなければ配列の中に探したい値を持った要素があるということなのでtrueを返します。
計算量は変わらずNのオーダーですが、ループの中にif文がない分、早くなっており定数倍の高速化が見込まれます。処理の数は単純に半分になっていますね。

問題を解いてみる

せっかくなので問題をときました。Aizu Online Judgeの線形探索の問題です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A

先ほど定義した関数を利用しています。

#include<iostream>
using namespace std;

bool linear_search(int A[], int n, int key) {
  int i = 0;
  A[n] = key;  // 番兵の設置
  while (A[i] != key) i++;
  return i != n;
}

int main() {
  int i, n, q, C = 0;
  int S[10001], T[501];
  // input
  cin >> n;
  for (i = 0; i < n; i++) cin >> S[i];
  cin >> q;
  for (i = 0; i < q; i++) cin >> T[i];

  // search
  for (i = 0; i < q; i++) {
    C += linear_search(S, n, T[i]);
  }

  cout << C << endl;
}