二分探索の更新・終了条件をしっかり理解する
よくバグらせがち
よくわからずbegin != endとして、プログラムが一生終了しないケースも...。
ある順序付集合$ \Zの区間$ Sに対して、次のような$ x \in \Zに対する条件$ P, Qが定まっていたとする。 $ P, Q: S \to { true, false }
i) $ t \in Sが存在して、$ x \leq tに限り$ P(x) = true（上限） ii) $ t \in Sが存在して、$ x < tに限り$ Q(x) = true（上界） なお、これらを解く二分探索アルゴリズムが得られれば、$ x > t, x \geq tの場合も$ P, Qを否定することで得られる。
本当は四つのパターンを全て列挙したかったがそれをすると大変な分量になるので、とりあえず議論がほぼ似通う二つを選び出した。
$ P, Qに関する$ tを求めたい。
$ P, Qの具体例
配列$ A = [0, 5, 10, 58, 63\rbrackに対して
$ P: A\lbrack x\rbrack \leq 50 ---> $ t = 2
$ Q: A\lbrack x\rbrack \leq 50 ---> $ t = 3
配列$ A = [0, 5, 10, \underline{50, 50, 50}, 63\rbrackに対して
$ P: A\lbrack x\rbrack \leq 50---> $ t = 5（上限）
$ Q: A\lbrack x\rbrack \leq 50 ---> $ t = 6（上界）
$ Pで解いた解に$ 1足せば$ Qの解が得られる。
以降、$ Sの要素が配列として、昇順に左から右に並べられている様子を想定する。
次の形式で記述する
code:cpp
while (継続条件):
mid = (begin + end) / 2
if P(mid) { (beginの更新) } else { end = mid; }
// if Q(mid) { (beginの更新) } else { end = mid; }
return (戻り値)
実装を見渡す限りいくつかの方式がある
alg-add) 1足す型
(beginの更新)をbegin = mid + 1と定める。
特徴: P(mid)がtrueと判定された時、次ステップの探索範囲からmidが省かれる
---> P(mid)がtrueと続く区間の上界を求めるのに便利 alg-hold) 保持する型
(beginの更新)をbegin = midと定める。
特徴: P(mid)がtrueと判定された時、次ステップの探索範囲からmidが省かれない
---> P(mid)がtrueと続く区間の上限を求めるのに便利 いずれでもmid = tとなるステップが必ず存在するため *2、この挙動はtを区間内に留められるか否かを判別することにおいて重要である。
知りたいこと
これら二つの実装の継続条件は何か？
終了時、どの変数（begin, end）を結果として返せば良いのか？
注
(*1) なぜ、半開区間[begin, end)？（Pだけについて考える）
1. P(mid)がfalseだったとき
次の探索範囲にmid値を含める必要はない
（P(x)がtrueとなる可能性のある場所xにしかtは存在しないから）
midを含めないようにする際の更新が楽
end = mid（こうすればmidは探索区間には含まれない）
2. end - beginが正しい区間長となり、中間となる位置を求めやすくなる
*2) 区間長の長さが$ 1になるまでにmid = tとなったか、ならなかったかで場合分けすると証明できる（はず）
区間長が$ 1に必ず到達するかどうか
結果は次のようにまとめられる。（細かな証明は後述）
Thm1, Thm2.) 条件$ P, Qのどちらであっても、探索区間の長さにおいて
alg-add) 長さ$ 0に到達できる
∵ begin = mid + 1と足しているせいで、P(mid)がtrueの時に区間長が0になりうる。
（長さが2の時を想定するとよい）
また、長さが$ 1の時、P(mid)の成否に関わらず次のステップで0になる。
alg-hold) 長さ$ 1に到達でき、長さ$ 0には到達できない。
∵ beginに1足していないことため、次のステップの長さは単調減少しつつも1以上に必ずなる。
また、長さが$ 1になってからは$ 1でとどまり続ける。
Thm3, Thm4) この状態に到達して、区間長の縮小が止まったら
条件$ P: P(t)がtrueになる場合
基本的には、P(mid)の真偽はmid <= tかmid > tかによって決定されるため、begin <= t < endが保たれる。
（midが、次のステップにおけるbeginかendかになることがこの性質の本質にあたる。）
alg-add) begin - 1, end - 1がt
∵ begin = mid + 1と1足していることに起因する。
mid = tとなったときP(mid)がtrueになり、beginはt + 1に配置される。
（tが[begin, end)区間から出てしまう）
さらに、その後のP(mid)はfalseになるので、beginはずっとその場所を保ち続ける。
長さが0に到達するまでにmid = tになるステップが絶対にあるので、begin = t + 1が最終状態になる。
alg-hold) beginがt
∵ mid = tとなったときP(mid)がtrueとなり、beginはtにとどまり続ける。
begin <= t < endが実行中常に保たれるため。
条件$ Q: Q(t)がfalseになる場合
Q(t)がfalseになるので、end = midの更新処理時にendにtが来る可能性がある。（t <= end）
alg-add) begin, endがt
∵ 更新時にbegin = mid + 1と$ 1足している
$ P(mid)がtrueならmid < tなので、begin = mid + 1 <= tとなる。
これにより、begin <= t <= endがアルゴリズムの実行中常に保たれ続けるため。
alg-hold) endがt（ただし、初期状態でt == beginとならないように注意する）
∵ 更新時にbegin = midと更新するため
$ Q(mid)がtrueならmid < tとわかり、beginの箇所にtが来ることはないから。
ただし、初期状態でt == beginであれば、beginにtが来る。
以上から見れば分かるとおり、これら四つを使い分けるのは困難である
beginとendに順序が存在するのが混乱の元になっている
実際には一方を条件を満たす側、もう一方を条件を満たさない側として、順序に依存せず一般化して扱うとよい。
ここからは、条件が$ P, Qのいずれであっても成り立つような性質を示し、停止可能性について議論する。 Thm.1 最小区間長への到達可能性
探索区間[begin, end)は、二分探索のwhileループのステップを経ることで
alg-add) 長さ$ 0の区間（begin == end）に到達する。
alg-hold) 長さ$ 1の区間（begin + 1 == end）に到達する。
証明
1.
alg-add) 長さ$ 0の区間から始めた場合、長さ$ 0の区間に到達している。
長さ$ 1の区間から始めた場合、長さ$ 0の区間に到達する。なぜなら...
$ mid = (begin + end) / 2
$ = (begin + begin + 1)/2
$ = (2begin + 1)/2
$ = begin
従って、$ P(mid)の成否に関わらず、次のステップで必ず$ begin = end（長さ$ 0）になる。
alg-hold) 長さ$ 1の区間から始めた場合、長さ$ 1の区間には到達可能である。
2.
長さ$ l \leq kの区間から始めた時に題意の区間長に到達したと仮定する。
長さ$ k + 1の区間では到達するか？$ \underline{k + 1 \geq 2}
https://scrapbox.io/files/6703cf2e9698c8001ce8ab8d.png
方針: 初めのwhileループのステップを踏むと区間の長さが$ l \leq k以下に縮むことを示し、帰納法の仮定を使う。
alg-add)とalg-hold)では証明の方針をほとんど共有しているので、違う部分だけそれぞれ示すようにする。
1. $ midの位置を除法切り捨ても含めて評価する。
$ end - begin = k + 1が成立する。
$ end = k + 1 + begin
このとき、$ midは$ (end + begin)/2 = (k + 1 + 2begin) / 2である。
偶奇にわけて考えれば、この値は次のように書き表せる
$ k = 2k'の時$ k' + begin
$ k = 2k' - 1の時も$ k' + begin
ただし、$ k \geq 1なので$ k' \geq 1である。
$ k' \leq kであることに注意appbird.icon
2. 求めた$ midに対して長さを求める。
$ P(mid) = false, $ Q(mid) = falseのとき
alg-a)でもalg-b)でもend = midと置換される。
$ mid - begin = (k' + begin) - begin
$ = k'
となり、いずれでも区間の長さは$ 1以上$ k以下になり、必ず探索範囲は縮まる。
$ P(mid) = true , $ Q(mid) = trueのとき
alg-addではbegin = mid + 1、alg-holdではbegin = midと置換される。
alg-add)では長さは次のように表せる。
$ end - (mid + 1) = end - (k' + begin + 1)
$ = k + 1 + begin - k' - begin -1
$ = k - k'
この長さは$ 0以上$ k未満である。
alg-hold)では、長さは$ end - (mid) = k - k' + 1となり、$ 1以上$ k以下となる。
まとめると、次のステップでは探索区間の長さは
alg-add)では$ 0以上$ k以下になる。
alg-hold)では$ 1以上$ k以下になる。
帰納法の仮定から、長さ$ k + 1の探索区間から始めた場合でも、題意の区間長に到達する。
注
何でこんなに証明長いの？区間の長さを$ 2で割ってるだけじゃないの？
切り捨て評価も含めてやってるから
とはいえど、アルゴリズムが長さlenベースで動いていればこれほど長くなくても済むかもしれない。
c.f. (accessed at 2024-10-08 22:59:08)の実装例 Thm2. 無限ループ可能性について
alg-hold) 探索区間[begin, end)は、長さ$ 0の区間（begin == end）に到達することはない
証明
「Thm1. 最小区間長への到達可能性」から、alg-hold)では長さ$ 1の区間に到達する時が存在する。
その時を取り上げて考えてみる。そのステップにおける$ midは次のようになる。
$ mid = (begin + end) / 2 = begin
ただ、alg-holdでは$ P(mid)の成否に関わらず、次のステップでも$ begin + 1 = endが成立する（長さ$ 1）。
長さ$ 1の区間に到達した地点で、長さ$ 0の区間に到達することはできない。
探索区間の長さはwhileループのステップ数に対して広義単調減少するので、長さ$ 0に到達することはない。 ここまでの成果で、何が言える？
alg-add) 終了条件をend - begin == 0とすれば、無限ループは発生しない。
alg-hold) 終了条件をend - begin == 1とすれば、無限ループは発生しない。
alg-hold) 終了条件をend - begin == 0とすると、無限ループする。
長さ$ 1に必ず到達してから、長さ$ 0に到達することはないから
ここからは、条件を$ P, Qに分けて、成り立つような性質を示す。
Thm.3 条件$ Pに対してどう動作するか？
探索範囲の長さが$ 0以上のとき、条件$ Pに対して
alg-add) $ begin \leq t < endとは限らない。
alg-hold) $ begin \leq t < endが成立する。
証明
0. 前提として、初期状態では$ begin \leq t < endである。
1. 二分探索の探索範囲が長さ$ k \geq 1であった場合を想定し、そこから一ステップ進めてみる。
$ midの定義と$ begin < endより、次が成立する
$ begin \leq mid < end
2. ここで、1ステップが終わった後、$ tがどこにあるかを調べる。
$ P(mid)がtrueのとき...すなわち、$ mid \leq tのとき
alg-add) begin = mid + 1であれば、次のステップにおいて$ begin \leq t < endとは限らない。
$ mid = tであったとき、この不等式が破られるappbird.icon *1
次のステップで$ begin = t + 1となり、$ t < beginとなる。
$ kの長さが$ 1
alg-hold) begin = midなので、次のステップにおいて$ begin \leq t < end
$ P(mid)がfalseのとき...すなわち、$ mid > tのとき
end = midとすれば、次のステップにおいて$ begin \leq t < end
次のステップにおいて$ tは$ beginと$ endの間に挟まれることになる。
つまり、$ k \geq 1までなら、これを無制限に適用し続けられ、その間$ tは$ beginと$ endの間にあり続ける。
まとめれば
alg-add)であれば、一度でも$ P(mid) = trueとなった場合$ begin \leq t < endとは限らない。
alg-hold)であれば、$ begin \leq t < endが成立する。
注
*1 この場合でも、答えの出力を工夫することで二分探索として動かせる。
Thm. 条件$ Pに対してalg-addを使うためには？
alg-add)において、$ mid = tになるステップは必ず存在する。
証明
この証明は厳密には間違っていて、alg-addアルゴリズムが長さ$ 1を経るとは限らないappbird.icon
長さ$ 2の場合も含めて証明できれば、すべてのケースを列挙できたことになる
そして、多分それはできる
i) 長さ$ 1になるまで$ mid = tになったことがある場合、
その$ mid = tになった以降のステップでは、$ beginは動くことはない。
∵ $ t < begin \leq mid、すなわち$ t < midなので、$ P(mid)は必ずfalseである。
i) 長さ$ 1になるまで$ mid = tになったことがない場合、
その時までずっと$ begin \leq t < endの関係は守られている
今、長さ$ 1であれば、$ begin = tといえる。
このとき、$ mid = beginとなるため、$ mid = tとなり、最終的に長さ$ 0に到達する。
いずれの場合でも、$ mid = tになった後は$ begin = t + 1が保たれる。
従って、これでも一応二分探索は正しく動作しており、長さ$ 0になったら$ begin - 1を出力すれば良い。
条件$ Pに対する解き方
終了条件
alg-add) end - begin == 0
alg-hold) end - begin == 1
戻り値
alg-add) begin - 1, end - 1
alg-hold) begin
Thm.4 条件$ Qに対してどう動作するか？
探索範囲の長さが$ 0以上の時、条件$ Qに対して
alg-add)$ begin \leq t \leq endが成立する。
alg-hold)$ begin < t \leq endが成立する（初期状態で$ begin \neq t）
証明
同様に、
Whileループ開始時の状態では$ begin \leq t \leq endが満たされている。
初期状態は$ t < endだが、それよりも条件を緩くしているappbird.icon
後述するように、$ Q(mid)がfalseになると$ t \leq endとなるため、条件を緩くしないとループが繋がらない。
各ステップでは$ begin \leq mid < endが成立する。
そこから一ステップ進めてみる。
$ Q(mid)がtrueのとき
すなわち、$ mid < tを考えたい。
ここで、$ mid + 1 \leq tであることに注意する。
alg-add)begin = mid + 1なので次ステップで$ begin \leq t \leq end
alg-hold)begin = midなので次ステップで$ begin < t \leq end
$ Q(mid)がfalseのとき
すなわち、$ mid \geq tのとき
end = midなので、次ステップで$ begin \leq t \leq end
従って
alg-add)では$ begin \leq t \leq end
alg-hold)では、
初期状態で$ begin = tだったとき*1、$ begin = t
そうでなければ$ begin < t \leq end
が常に成立する。
注
*1) この場合、長さが1になるまでP(mid)からはずっとfalseが出続ける。
そのため、終了時にbegin == t, end == t + 1が成立する。
begin == t, end = t + 1
条件$ Qに対する解き方
終了条件
alg-add) end - begin == 0
alg-hold) end - begin == 1
戻り値
alg-add) begin, end
alg-hold) end（ただし、初期状態でt == beginとならないように注意する）