Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の6_C問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#6では、「二分探索」というテーマで学びます。
#3から#6は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。
問題（6_C: Lower Bound）
問題はリンク先をご覧ください。
指定された値以上の値が現れる最初の位置を返す lower_bound について学びます。
std::lower_bound について
以下は、cpprefjp 様の記事を参考にさせていただきました。
std::lower_bound は、ソート済みイテレータ範囲において、指定された要素以上の値が現れる最初の位置のイテレータを返します。
template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value);この関数は、[first , last) の範囲で二分探索を行い指定された値 value を見つけることができます。
最大で、log2 (last – first) + O(1) 回の比較を行います。
6-A で学んだ binary_search との違いは、値が見つからない場合に、指定された値以上の最初の位置のイテレータを返します。false を返すだけの binary_search よりも、リッチな情報を得ることができます。
lower bound を読み替えると、「k より真に小さい要素の個数」と言えます。似た関数で upper_bound がありますが、こちらは「k 以下の要素の個数」を求めることができます。upper_bound から lower_bound を引くと、k と一致している要素の個数を求めることができます。
これらの利点があり、C++ では、binary_search 関数はそれほど見かけず、lower_bound（または upper_bound）が使われています。
C++ プログラム例（ITP2 6_C）
与えられた数列 A に対して、「クエリとして与えられた値 k の lower bound を求めてください」と問題文でなっています。
イテレータを要素の個数に変換するために a.begin() を引いて出力しています。
以下は、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;
auto it = lower_bound(a.begin(), a.end(), t);
cout << it - a.begin() << endl;
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
最初に lower_bound の仕様を読んだときに binary_search の方が使いやすいと思いました。しかし、二分探索を使う局面で実際に使ってみて、lower_bound の方が得る情報が多いため、役立つことが分かりました。
引き続き、ITP2 の問題を紹介していきます。
