Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の4_B問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#4「探索」は、線形探索、二分探索、ハッシュ（辞書）を学びます。
問題（4_B: Binary Search）
問題はリンク先をご覧ください。
AOJ ALDS1 4_B問題: Binary Search
二分探索について学びます。
二分探索について
二分探索は、整列されたデータを前提とします。基本的な考え方は以下です。
- 真ん中の値を調べる。
- 真ん中の値が条件を満たせば、それを返す。
- 条件を満たす値が前半にあれば、前半を（再帰的に）調べる。
- 条件を満たす値が後半にあれば、後半を（再帰的に）調べる。
調べる範囲が半分になっていくため、計算量は、$O(log N)$ となります。問題に紹介されている擬似コードは以下です。
binarySearch()
left = 0
right = n
while left < right
mid = (left + right) / 2
if A[mid] == key
return mid
else if key < A[mid]
right = mid
else
left = mid + 1
return NOT_FOUND二分探索は、高速で動作する応用範囲が広いアルゴリズムです。
C++ プログラム例（ALDS1 4_B）
与えれた問題の構造は、前回に紹介した 4_A と同じです。
二つの配列 s と t を読み込みます。t の要素に対して s に含まれている要素の個数を出力します。4_A と異なり s の大きさ n の上限は 105、t の大きさの上限 q は 5×104 です。
n × q の上限が 5 × 109 となり、線形探索では間に合いません。実際、4_A 問題のプログラムを提出すると TLE（Time Limit Exceeded）判定となります。
ただし、「$S$ の要素は昇順に整列されている」という制約が追加されています。このため、（ソートをしないで）二分探索を使うことができます。
二分探索の擬似コードは、key と等しいインデックスを返しています。実装例では、key と一致した要素が含まれているか bool 型を返すように変更しました。結果的に 4_A のプログラムとは、関数 search のみの違いとなります。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
bool search(vector<int> a, int key)
{
int left = 0;
int right = a.size();
int mid;
while (left < right) {
mid = (left + right) / 2;
if (a[mid] == key) {
return true;
} else if (key < a[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return false;
}
int main()
{
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int q;
cin >> q;
vector<int> t(q);
for (int i = 0; i < q; ++i) {
cin >> t[i];
}
int result = 0;
for (int i = 0; i < q; ++i) {
if (search(s, t[i])) {
++result;
}
}
cout << result << endl;
return 0;
}標準ライブラリ binary_search を使う。
「プログラミング応用」（ITP2）の6_A問題で、標準ライブラリとして実装されている binary_search を紹介しました。
main 関数だけ見れば、binary_search を呼び出す行（24行目）しか差がありません。標準ライブラリ binary_search を使ったプログラムは以下となります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int q;
cin >> q;
vector<int> t(q);
for (int i = 0; i < q; ++i) {
cin >> t[i];
}
int result = 0;
for (int i = 0; i < q; ++i) {
if (binary_search(s.begin(), s.end(), t[i])) {
++result;
}
}
cout << result << endl;
return 0;
}標準ライブラリ lower_bound を使う。
「プログラミング応用」（ITP2）の6_C問題で、標準ライブラリとして実装されている lower_bound を紹介しました。
binary_search と同じ二分探索を使ったライブラリ関数ですが、真偽値しか返さない binary_search と比較して、指定した値以上の最初の位置を返すため、よりリッチな情報を返すと考えることができます。実際に競技プログラミングでは、binary_search ではなく、lower_bound（もしくは upper_bound）がよく使われています。
標準ライブラリlower_bound を使ったプログラムは以下となります。差分は24行目だけです。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int q;
cin >> q;
vector<int> t(q);
for (int i = 0; i < q; ++i) {
cin >> t[i];
}
int result = 0;
for (int i = 0; i < q; ++i) {
if (*lower_bound(s.begin(), s.end(), t[i]) == t[i]) {
++result;
}
}
cout << result << endl;
return 0;
}上記プログラムはどちらも、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
この問題では、二分探索を学びました。ある値が配列に含まれているか確認するために使いましたが、応用範囲が広いアルゴリズムです（応用問題は4_Dで紹介します）。
引き続き、ALDS1 の問題を紹介していきます。
