C++で二分探索を実装する - プログラミング原人の進化論

探索アルゴリズム第2弾、前回の線形探索に引き続き、今回は二分探索についてまとめました。

* 目標

二分探索を実装できるようになる。

二分探索

二分探索は、整列された配列に適用できる高速な探索方法です。あらかじめ整列されている必要があることに注意が必要です。この記事では昇順に整列されている場合を考えます。
全体を２分割して、キーが含まれている方を選ぶ（昇順となっていることから、どちらにキーが含まれているかわかります）、ということを繰り返します。
最悪の手数をxとするとは $2^x = N$ より計算量は $O(log N)$ となることがわかります。

アルゴリズム

列全体を探索範囲とする
以下を繰り返す：
1. 探索範囲の中央の値とキーを比較する。一致すれば終了。
2. 中央の値がキーより小さいならば後半部を、中央の値がキーより大きいならば前半部を探索範囲とする。

実装してみる

与えられた配列の中に、目的のキーを持った要素が含まれているか判定する関数を定義してみます。要素は整数とします。
探索範囲を制限するための変数leftとrightおよび探索範囲の中央を表すcenterを移動させることで、探索範囲を表現します。

bool binary_search(int A[], int n, int key) {
  // A[]: 探索の対象となる配列を格納, n: 配列の要素の数
  int left = 0, right = n, center;

  while (left < right) {
    center = (left + right) / 2;
    if (A[center] == key) return true;
    else if (A[center] > key) right = center;
    else left = center + 1;
  }
  return false;
}

問題を解いてみる

せっかくなので問題を解いてみます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp

先ほど定義した関数を利用すると次のようになります。

#include<iostream>
using namespace std;

bool binary_search(int A[], int n, int key) {
  int left = 0, right = n, center;

  while (left < right) {
    center = (left + right) / 2;
    if (A[center] == key) return true;
    else if (A[center] > key) right = center;
    else left = center + 1;
  }
  return false;
}

int main() {
  int i, n, q, C = 0, S[100000], T[50000];

  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 += binary_search(S, n, T[i]);

  cout << C << endl;
  
  return 0;
}