lower_bound, upper_bound、結局どっちを使えばいいの？ってなる場面が多かったので、メモがてらに書いてみる。この記事では直感的にlower_boundやupper_boundが使いこなせるようになることを目指す。例えば、

vector<int> v = {40, 20, 20, 19, 1};

と降順に並ぶ配列に対して41, 40, 39, 21, 20, 19, 18, 2, 1, 0などをkeyとしたとき、lower_bound, upper_boundをどう使えばいいのか、そしてそれがどこのイテレータを返すのかがすぐ分からない人に向けての記事になる。あくまで一つの覚え方であることには留意してほしい。

###注意事項(よまなくてもいい)
前提として、今回使うコンテナはvectorである。また、配列はすでにsort済みであるとする。C++11からsort済みでなくてもある基準を満たしていればlower_boundやupper_boundを使うことはできる( 参考：https://cpprefjp.github.io/reference/algorithm/lower_bound.html )が、今回は無視する。

#昇順の配列に対する使い方

vector<int> v = {1, 1, 1, 2, 2, 3, 3, 3, 5};

に対して使ってみる。例えば2をkeyとして二分探索するには、単純に

lower_bound(v.begin(), v.end(), 2);
upper_bound(v.begin(), v.end(), 2);

とかけばよい。そして、これらは何を返すだろうか。次のように考えるとわかりやすい：

keyを割り込ませて、残りを右にずらしたとき、配列はsortされたままであるような位置のイテレータを返す。そして、lower_boundはそのような位置の中で一番左(ゆえにlower)、upper_boundは一番右(ゆえにupper)の位置を返す。

次の図をみればわかると思う(key = 0, 1, 2, 3, 4, 5, 6)。
key = 0のとき

key = 1のとき

key = 2のとき

key = 3のとき

key = 4のとき

key = 5のとき

key = 6のとき

gif

言い方を簡潔にすれば、sort済みの配列の順序を崩さないようにkeyを入れるとき、最左(または最右)でどこに入れられるかを返すということである。
この覚え方の利点は、「以上」「より大きい」といった言葉に頼らずにすむのでv.end()がいつかえってくるか？など直感的にわかり、しかもlowerやupperという名前も理解に結びつく。更に、降順の配列にもlower_boundやupper_boundを使うことができるようになる。

#降順の配列に対する使い方

vector<int> v = {5, 3, 3, 3, 2, 2, 1};

に対して使ってみる。例えば2をkeyとして二分探索するには、

lower_bound(v.begin(), v.end(), 2, greater<int>());
upper_bound(v.begin(), v.end(), 2, greater<int>());

とかけばよい。第四引数は、「配列がどのようにsortされているか？」をlower_bound, upper_boundに伝える役目を果たしている(ここでは、greater、つまり>なので降順)。デフォルトでは昇順であることを想定している。前章を踏まえれば、降順の配列の順序を崩さないようにkeyを入れるとき、最左(または最右)でどこに入れられるかを返すのがわかる。とすれば、key=2のときはlower_boundはv[4]のイテレータを返し、upper_boundはv[6]のイテレータを返す、ということが容易にわかる。