回転ソート配列での探索

[1, 2, 3, 4, 5] を途中でぐるっと回すと [4, 5, 1, 2, 3] のようになります。これを回転ソート配列と呼びます。全体としては並んでいないのに、半分を捨てる方法が使えます。

真ん中と比べても、行き先が決まらない

[4, 5, 6, 7, 0, 1, 2] から 0 を探します。真ん中は 7 です。0 は 7 より小さいので左へ、と考えると外れます。0 は右側にいます。

並んでいる配列なら「真ん中より小さければ左」と言い切れました。この配列は途中で一度だけ値が落ち込むので、その言い切りが成り立ちません。真ん中の値と目当ての値を比べるだけでは、どちらへ進めばよいか決まらないのです。

半分に割ると、片側は必ず並んでいる

ここで効いてくるのが、落ち込む場所が 1 か所しか無いという性質です。どこで半分に割っても、落ち込みはどちらか一方の側にしか入りません。つまり反対側は、途中に落ち込みが無く、きれいに並んでいます。

どちらが並んでいる側かは、その区間の先頭と真ん中を比べれば分かります。先頭のほうが小さいか同じなら、その区間は落ち込みを含まず、きれいに並んでいます。先頭のほうが大きければ、その区間のどこかで落ち込んでいます。

比べるのは 2 つの値だけで、区間の中を歩き回る必要はありません。だからこの判定は 1 回の比較で済み、半分を捨てる速さを損ないません。

並んでいる側だけ、範囲で判定する

並んでいる側が分かれば、あとは簡単です。その側は端から端まで昇順なので、目当ての値がその両端の間に収まっているかどうかを見るだけで、そこに含まれるか含まれないかが確定します。

含まれていればそちらへ進み、含まれていなければ反対側へ進みます。反対側の中身は一切調べません。並んでいない側について何も分からなくても、並んでいる側に無いと分かれば十分だからです。

こうして毎回どちらか半分を捨てられるので、回転していても、普通に並んだ配列と同じ回数で終わります。

回転しているかどうかを先に調べる必要もありません。まったく回転していない配列を渡しても、毎回「左側が並んでいる」と判定されて、そのまま正しく動きます。場合分けを 1 つ減らせるので、判定用の前処理は書かないでください。

端と等しい値を、取りこぼさない

範囲に収まっているかを判定するとき、両端そのものと等しい場合を含めるかどうかで結果が変わります。等号を 1 つ落とすと、端にある 1 件だけが見つからなくなります。

要素が 2 個しかない配列や、真ん中が先頭と重なる場面でこの差が出ます。[4, 5, 6, 7, 0, 1, 2] で 4 を探す、5 を探す、2 を探す。この 3 つを手で追ってみて、境目にある値を落としていないかを確かめてください。

真ん中の値そのものが目当ての値だった場合も、範囲の判定に入る前に決着させておく必要があります。ここを後回しにすると、どちらの側にも含まれないと判定されて取りこぼします。

1. O(log n) で実装する
2. 重複なし配列を前提とする
3. 見つからない場合は -1 を返す