lower_bound で混乱している人かわいそう

言語さんサイドにも問題があるというのはそうかも。

とはいえ、理解が足りないまま「わかりにくい」と言っている人はかわいそうなので、解説をします。

名前について

なんで「x 以上の最小値を得る関数」が lower_bound と呼ばれているのかわからん*1

まず、それを得る関数ではないです。イディオムとしてそう覚えてしまっているような人が多いため、こうなってしまう人が多い気はします。

実際には値ではなくイテレータを返すもので、「x と等価 (equivalent) な値がある区間の下限の位置」が返ってきます。ここでの equivalent というのは == とは違う概念なのですが、とりあえず（int のような型では）== と同一視してよいので、詳細は後述とします。

また、upper_bound についても同様で、「x より大きい最小値を得る関数」ではなく、「x と等価な値がある区間の上限の位置を返す関数」です。区間は半開区間の形で表されることに注意します。

5 と等価である区間の例の図です：

[1, 3, 5, 5, 6, 7]
       [----)
       L    U

つまり、[lower_bound, upper_bound) の区間が、x と等価な区間ということになります。lower_bound と upper_bound のペアを返す、equal_range という関数もあります。

等価な値がないケースに関して補足

より厳密には「x 未満の区間と x 以上の区間の境界」「x 以下の区間と x より大きい区間の境界」として定義されているので、たとえば先の例での “4 と等価である区間” は次のような空区間になります。

[1, 3, 5, 5, 6, 7]
     [)
     LU

そうした境界がない列（[1, 8, 5, 5, 3, 6, 5] で x = 5 など）については未定義動作なので、C++ 側はそういう入力がないと仮定して問題ありません*2。ここで境界と言っているのは、「その境界で以って配列を二分割できる」というものであり、そうした境界が存在しないからだめということです。

なお、そうした境界さえあれば、ソート済みである必要はありません。たとえば [1, 4, 2, 5, 5, 8, 5, 6] で x = 5 は、lower_bound であれば問題ありません（upper_bound はだめ）。 [1, 4, 5, 5, 7, 6, 8] で x = 5 は、lower_bound も upper_bound も問題ありません。

よくあるイディオムについて

*std::lower_bound(_, _, _) で一つのイディオムとして覚えていると、こうした「境界」を意識しないようになってしまう気がします。わかった上で思考をスキップしているのであれば問題ないとは思いますが、知らずにやっていると混乱の元になりそうです*3。

[1, 3, 5, 5, 6, 7]
       [----)
       L    U

ここで、*L や *U としてアクセスすると 5 と 6 が返ってくるので、結果的にはよくある「5 以上の最小値」「5 より大きい最小値」のようになります。

当然、L U が配列の末尾を指していた場合（全部の要素が 5 未満・以下の場合）は配列外参照で未定義動作なので注意が必要です。「値が返ってくる」という認識だと、こういうケースでバグらせて逆ギレしそうです。

equivalence について

x == y のとき x is equal to y と言い、y <= x && x <= y（より言語仕様っぽく言えば !(x < y) && !(y < x)）のとき x is equivalent to y と言います。前者における “等しさ” を equality と言い、後者における “等しさ” を equivalence と言います。 x <= y は x < y || x == y ではなく !(y < x) として（< の形で）扱われることに注意や慣れが必要です。

< は strict weak ordering と呼ばれる順序を成している必要があります。これは、次の 4 つの条件で表されます。

!(x < x)
- 「自身が自身より大きい」ということにはならない
x < y ならば !(y < x)
- 「相手が自分より大きいのに、自分も相手より大きい」ということにはならない
x < y && y < z ならば x < z
- 「自分より大きい相手よりさらに大きい（別の）相手は、自分より大きい」
equiv(x, y) を !(x < y) && !(y < x) で定義するとき、equiv(x, y) && equiv(y, z) ならば equiv(x, z)
- 「x と比較不能である」ということを「x と “等価” である」ということにできる
  - !(x < y) && !(y < x) を「x と y は比較不能である」と言う
  - 「equiv(x, y) && equiv(y, z) ならば equiv(x, z)」などの性質から equiv は同値関係を成している

「x と比較不能である」を「x と等価である」と言えない状況の例を考えてみます。x < y を x.first < y.first && x.second < y.second で定義しようとしてみます。このとき、x = {2, 2}, y = {3, 0}, z = {1, 1} のようにすると、equiv(x, y) && equiv(y, z) ですが z < x なので equiv(x, z) ではありません。 C++/STL の関数の順序を扱う関数（std::sort など）の多くは strict weak ordering を仮定しているため、そうでない順序を与えようとすると、やはり未定義動作となります*4。ソートしようとして、無限ループになったり配列外参照が起きたりすることもあります。

そこで、例えば「10 で割った値での比較による順序」を考えます。std::sort など同様に比較関数を渡せます。

int main() {
    std::vector a{12, 10, 13, 21, 20, 25, 31, 32};
    auto div10 = [](auto x, auto y) { return x / 10 < y / 10; };
    auto [lb, ub] = std::equal_range(a.begin(), a.end(), 24, div10);
    // [12, 10, 13, 21, 20, 25, 31, 32]
    //              [----------) <- この区間となる
    //              L          U
}

ここでは 21 と 24、20 と 25 などが equivalent であることに注意しましょう。他にも、「（pair の）first だけの比較による順序」なども定義できそうです。

クイズ：先の例 x.first < y.first && x.second < y.second と逆に、x.first < y.first || x.second < y.second とした場合の順序ではどうでしょうか？

こたえ

x = {0, 1}, y = {1, 0} とすると、x < y && y < x となり、ふたつめの条件に反してしまうのでだめ。

二分探索について

名前が二分探索っぽくない

それはそうかも。

ところで、名前が二分探索っぽい bsearch は二分探索であることが特に規定されていません。std::binary_search はさすがに規定されていそう。

さておき、この手のものを求める関数で線形探索をされたらさすがに困るので、二分探索であってほしいという思いはある程度自然だと思います。「境界が存在する」という仮定*5があるので、線形探索をしたいとはならないでしょう。

ここで、「set のイテレータに対してこれを行うと線形時間かかるから、set の場合は線形探索をしている」と思い込む人もよくいるようです。そうではなくて、（set というかランダムアクセス可能でないイテレータ一般に）イテレータの移動に関してその時間がかかるだけで、比較回数は \(\log_2(n)+O(1)\) 回であり、二分探索をしています。

比較のコストがとても高いクラスを入れたデータ構造で二分探索をしたくて、かつそのデータ構造ではランダムアクセスが高速にできない状況とかを考えると、うれしいかもしれません？とはいえ、ランダムアクセスイテレータのみに対して提供する関数だった方が、幸福度が高かったような気もします。

set の場合でも対数時間だと思っている人もいますが、そうできない理由と解決策に関してはこちらの記事で書いています。ざっくり言うと、イテレータだけ渡された関数にとっては、元のコンテナが二分木ベースであることを活かした探索をできないためです。

別の言語の例

C++ では、set から「x 以上の最小値」「x 以下の最大値」を得たいときに

auto it = set.lower_bound(x);
if (it != set.end()) {
    auto ge = *it;
}

とか

auto it = set.upper_bound(x);
if (it != set.begin()) {
    --it;
    auto le = *it;
}

などと書く必要があり、煩雑かつバグらせやすいです。あるいは「x 未満の最大値」などはどうでしょうか？

やりたいことは「x 以下の最大値を得る」などであって、「x と等価な区間の上限が先頭でなければその区間の一つ前にある値を得る」などではないはずです。これは、「0 から n-1 までの値を順に得たい」をしたいのに「i を 0 で初期化して i が n 未満である限り i の値を得て処理してから i をインクリメントする」などをする必要があるのと似ています。

Rust では、以下のように書けます。

if let Some(ge) = set.range(x..).next() {
    // ge は x 以上の最小値
}

if let Some(le) = set.range(..=x).next_back() {
    // le は x 以下の最大値
}

if let Some(lt) = set.range(..x).next_back() {
    // lt は x 未満の最大値
}

「x 以上の区間の最初の値」や「x 以下・未満の区間の最後の値」などという意味合いとして書け、直感的なのではないでしょうか。

if let Some(lt) = set.range(..x).next() と書いてバグらせる人*6もいますが、それは仕方ないですね。

他の言語や他のデータ構造の文脈に関して

Python で「x より大きい・小さい、最小・最大の値は？」のような形式のクエリ（特に学術界隈*7では successor query や predecessor query などと呼ばれることが多い気がします）に答えるデータ構造を実装する際、わざわざ lower_bound などと命名する人がそこそこいる印象がありますが、多くの場合は位置ではなく値を返しているでしょうから、そうした命名がうれしいとは思いにくいです。

シンプルに max_less とか min_greater_equal とか名づける方がわかりやすいのではないでしょうか。

その他の命名例

max_less
- max_lt less lt strict_predecessor predecessor pred pred_exclusive
- strict の代わりに proper とかもあるかも
- t は (less) than の t
max_less_equal
- max_le less_equal le predecessor pred_inclusive pred
min_greater
- min_gt greater gt strict_successor successor succ succ_exclusive
min_greater_equal
- min_ge greater_equal ge successor succ_inclusive succ

狭義（= 含まない）と広義（= 含む）のどちらを単に predecessor と呼んで他方を **clusive などと呼ぶかは人によりそうです。

これは横道ですが、x <= y は x is less than or equal to y です。x is less than or equal y と言ってしまう人がそこそこいる印象があります。x is less than or equals y なら valid な感もありそうですが、あまり一般的ではないような気がします。

C++ で何らかの別のデータ構造を実装するときも、競プロ文脈ではイテレータを返したいことは稀でしょうから、わざわざ bound 系の命名に固執する必要はない気がします。

んーでも suffix array に処理させるクエリとかだと区間を返してほしくなることもありそうだから、そういうときは bound なり range なりの名前がうれしいかも？と思いました。

おわり

にゃんにゃこにゃ

会社の人とおしゃべりしてるときに「夏休み中は未履修のアルゴリズムの勉強に時間を充てたいので、お気持ち表明ブログは書きません」みたいなことを言った記憶があるものの、やっぱり書きたくなってきちゃった
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年8月12日

すみません、このテーマ以外にも表明したいお気持ちがあるので、たぶん近いうちにまだ書きます。

*1:こういった旨のことを言っている人はたくさん見た気がしていて、特定の人を揶揄する意図はありません。

*2:そういう入力を与えた場合はユーザに責任があるのであって、C++ 側は悪くないという感じ。

*3:競プロ、強い人の真似をしようとしてそういうタイプの混乱をするのがよくありそう。

*4:ユーザに責任があって C++ 側に責任はないということ。口を酸っぱくして言っている。

*5:存在しない場合は妥当な返り値が存在しない上、存在性の判定には計算量を（最悪時）線形にする必要があるのでユーザに責任を押しつけたい。

*6:えびちゃんです。

*7:学術界隈という用語が競プロ界隈語っぽい。アカデミック文脈？みたいな意味合いのつもりです。

えびちゃんの日記

えびちゃん（競プロ）の日記です。