二分探索と三分探索
ちょっと考えたことをまとめてみました。どちらのアルゴリズムも区間を扱うものですが、例によって私の好みで半開区間を主に扱います。
二分探索とは何か
自分なりにまとめると、「ある点を境界に真偽が入れ替わるとき、その境界を効率的に求めるアルゴリズム」だといえます。二分探索という単語は「単調性」や「最大/最小」というキーワードとともに語られることが多いように思いますし、実際問題それらが要求されることが非常に多いのですが実はそれらがなくても二分探索は成立します。
「ある点」というのが区間内に複数(あるいは0個)あっても適当に番兵を置けばどれか一つを検出できます(どれが検出されるかは分からないし、番兵が検出されるかもしれない！)。以下の図でいうと、黒い丸で囲んだ点のどれかを検出できます。もちろん、少し手を加えれば赤-青の境界のどれかを検出するようにすることもできます。
単調性というのは「ある点」が一つしかないことを保証しているだけです。また、二分探索においては連続か離散か(実数か整数か)はあまり気にしなくてよい要素です（もちろん実装上の細かい注意点は多少変わりますが）。
二分探索の原理
「珠玉のプログラミング」という本や様々なweb上の資料などで分かりやすく説明されています。不変条件はとても大事です。
整数の二分探索の実装
色々書き方がありますが、私は蟻本のlower_bound風な実装が好きです。考えている区間が[from, to)であるとき、開区間風にlow = from - 1, high = to からスタートします。こうすると、from-1やtoが番兵(それぞれ、常に真/偽を返すものだと思う)として機能し、考えている区間内で常に真であるときや常に偽であるときによい目印になってくれます。二分探索内でcheck(from-1)やcheck(to)が実際には呼び出されないこともポイントです(セグフォの心配などをしなくてよい)。
三分探索とは何か
二分探索に比べると複雑なので、実数の場合についてのみ述べます。「unimodalな関数に対して、区間内での最大値を効率的に求めるアルゴリズム」というのが今の認識です。unimodalな関数というのは、高々1点を境界に増加、減少が入れ替わるような関数のことです。三分探索は凸というキーワードとともに語られることが非常に多いのですが、それは十分条件にすぎません。つまり、凸ならばunimodalなのであって、逆は必ずしも成り立つわけではありません。(凸という言葉をunimodalの意味で使っている人が多いだけなのかもしれませんが）
整数の三分探索
実は三分探索なんて使わなくても二分探索に帰着させることで問題は解決できます。つまり、階差数列がある点を基準に0より大きいか0以下になるかが切り替わるとき、区間内での最大値を効率的に求めることができます。
要するに、階差数列が{+, +, +, ..., +, 0, 0, ..., 0, 0, -, -, ..., -}となっていればよいです（ちなみに、実数版では微分係数の符号で考えれば殆ど同じだと気づきます）。てっぺんの右側と左側の両方に平らな部分があるとうまく行かないことに注意してください。{+,0,+,...,+,0,...,0,-,...,-,0,0,-,...}みたいなのは原理的に無理です。クロネッカーのデルタとかを考えると、これはどうやっても効率的に最大値を求めるなんてできません。
もちろん、区間内で広義単調減少や広義単調増加であるときも同様に求めることができます。
以下実装を見てみます。条件によって等号を付けるかどうかが変化するので注意してください。
//[from, to)におけるunimodalFuncのargmax(もし複数ある場合は一番若い番号)を返す int findMaximal(int from, int to) { // d[i] = a[i] - a[i-1]とする。 // このとき、d[i] > 0 <=> a[i] > a[i-1]なので、 // d[i] > 0なる最大のi in (from, to)を見つけると、a[i]が最大値 for (;to - from > 1;) { int mid = (from + to) / 2; (unimodalFunc(mid) - unimodalFunc(mid - 1) > 0 ? from : to) = mid; } return from; }
これだけシンプルに書けるのならもう整数の三分探索なんていらないや、という気分になってしまいます。
