AOJ ITP2 6_A（Binary Search）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の6_A問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#6では、「二分探索」というテーマで学びます。

#3から#6は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。

問題（6_A: Binary Search）

問題はリンク先をご覧ください。

AOJ ITP2 6_A問題: Binary Search

二分探索法によって要素の検索を行う binary_search について学びます。

std::binary_search について

以下は、cpprefjp 様の記事を参考にさせていただきました。

std::binary_search は、二分探索法を使って、指定された範囲の一致する要素の検索を行います。

  template <class ForwardIterator, class T>
  bool binary_search(ForwardIterator first,
                     ForwardIterator last,
                     const T& value); 

[first, last) の要素は、ソートされている必要があります。[first, last) 内のイテレータで、*i == value であるような要素が見つかれば、true を返し、それ以外の場合は、false を返します。

最大で、log2 (last – first) + O(1) 回の比較を行います。

C++ プログラム例（ITP2 6_A）

数列 A に k₁、k₂、…、k_q が存在するか判定します。binary_search が true を返せば 1 を出力して、それ以外の場合は、0 を出力します。

以下は、C++のプログラムです。

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int t;
		cin >> t;
		if (binary_search(a.begin(), a.end(), t)) {
			cout << 1 << endl;
		} else {
			cout << 0 << endl;
		}
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

C++ では、戻す情報量が多い、lower_bound を使う場合が多いです。binary_search は true/false だけが欲しい場合に使ってみても良いかもしれません。

引き続き、ITP2 の問題を紹介していきます。