「ソートも、サーチも、あるんだよ」
～標準C++ライブラリにみるアルゴリズムの面白さ

＜algorithm＞のソートたち

ソート列に対する二分検索

　ところで僕らはなぜソートするのでしょうか。大きな理由の一つは「ヒトが順序正しく並んだ列を求めるから」、もう一つはより速く検索するためです。N個の要素がデタラメに並んでいるとき、特定の要素がその中に存在するか否かを判定するのに要する時間は（結局アタマからケツまで順に調べるしか判定するすべがないのだから）要素数Nに比例します。時間計算量Ο(N)ですね。一方、N個の要素がソートされていれば二分検索ができるのでΟ(logN)になります。Ο(N)に比べれば劇的なスピードアップが見込まれます。

　<algorithm> が提供する（ソートされた列に対する）二分検索アルゴリズムは binary_search, lower_bound, upper_bound, equal_range の4つ。順に見ていきましょう。

binary_search

　ソートされた要素列内に指定した要素が存在すればtrue,さもなくばfalseを返します。

array<int,10> a = { 0, 1, 2, 2, 5, 7, 7, 8, 8, 9 };

// 5, 3 は配列内にあるか?
bool found;
found = binary_search(a.begin(), a.end(), 5);
cout << "5: " << (found ? "found." : "not found.") << endl;
found = binary_search(a.begin(), a.end(), 3);
cout << "3: " << (found ? "found." : "not found.") << endl;

　要素の有無を調べるだけなら binary_search() で十分ですが、binary_search() は見つかった位置を教えてはくれません。それが知りたいなら lower_bound, upper_bound, equal_range を使うことになります。

lower_bound, upper_bound, equal_range

　ソートされた列に新たな要素を挿入する際の挿入位置を返してくれます。

　例えば列: { 0, 1, 2, 2, 5, 7, 7, 8, 8, 9 } に 2 を挿入するとき、

{ 0, 1, 2, 2, 5, 7, 7, 8, 8, 9 }

　下線を引いた要素の直前に挿入可能ですね。lower_bound() は列の先頭に最も近い挿入位置、upper_bound() は先頭から最も遠い挿入位置を返します。equal_range() は lower_bound() と upper_bound() の結果の pair、すなわち指定した要素に等しい要素列の範囲を返してくれます。

　同様に 6 を挿入するなら:

{ 0, 1, 2, 2, 5, 7, 7, 8, 8, 9 }

　lower_bound(), upper_bound() 共に下線要素の位置を返します。

template<typename Iterator>
void print(Iterator first, Iterator last, Iterator lower, Iterator upper) {
  for ( Iterator iter = first; iter != last; ++iter ) {
    if ( iter == lower && iter == upper ) { cout << "[]"; }
    else if ( iter == lower ) { cout << " ["; }
    else if ( iter == upper ) { cout << "] "; }
    else cout << "  ";
    cout << *iter;
  }
  cout << endl;
}
...
array<int,10> a = { 0, 1, 2, 2, 5, 7, 7, 8, 8, 9 };
array<int,10>::iterator lower, upper;

// 配列内での 2 の位置
lower = lower_bound(a.begin(), a.end(), 2);
upper = upper_bound(a.begin(), a.end(), 2);
cout << "2: ";
print(a.begin(), a.end(), lower, upper);

// 配列内での 6 の位置
lower = lower_bound(a.begin(), a.end(), 6);
upper = upper_bound(a.begin(), a.end(), 6);
cout << "6: ";
print(a.begin(), a.end(), lower, upper);

// 配列内での 2 の位置
auto range = equal_range(a.begin(), a.end(), 2);
lower = range.first;
upper = range.second;
cout << "2: ";
print(a.begin(), a.end(), lower, upper);

// 配列内での 6 の位置
range = equal_range(a.begin(), a.end(), 6);
lower = range.first;
upper = range.second;
cout << "6: ";
print(a.begin(), a.end(), lower, upper);