ピーク要素検索

両隣より大きい要素を頂上と呼びます。[1, 3, 5, 4, 2] なら 5 の位置が頂上です。この配列は並び替えられていないのに、半分を捨てる方法が使えます。それがなぜ成り立つのかを見ていきます。

並んでいないなら、全部見るしかない気がする

素直に考えると、全部の要素について左右の隣と比べていくしかありません。要素が 100 万件あれば 100 万回です。

半分を捨てられたのは、これまで配列が昇順に並んでいたからでした。今回はその保証がありません。真ん中を見ても、そこより左に大きい値があるのか右に大きい値があるのかは、何も決まっていないように見えます。

配列の最大値は必ず頂上になります。ただし最大値を探すには結局すべての要素を見ることになるので、これでは何も速くなりません。

登り坂の先には、必ず頂上がある

ところが、この問題には別の保証があります。ある位置とその右隣を比べて、右隣のほうが大きかったとします。つまり今いる場所は登り坂の途中です。

このまま右へ進み続けると、どこかで下り始めるか、下らないまま右端に着くかのどちらかです。下り始めた直前の地点は両隣より高いので頂上です。右端まで登りっぱなしなら、右端が頂上です。どちらに転んでも、右側には必ず頂上があります。

逆に右隣のほうが小さければ、今いる場所は下り坂の途中か、そこ自体が頂上です。どちらにしても、今いる場所を含む左側に必ず頂上があります。

どちらの場合も「頂上を含むほうの半分」が言い切れるので、もう半分は捨ててよいことになります。並び順ではなく、この言い切りが根拠になっているわけです。捨てた側にも頂上があるかもしれませんが、それは構いません。ほしいのはどれか 1 つだけだからです。

比べるのは真ん中とその右隣の 2 つだけで、左隣は見なくても進む方向の判断がつきます。範囲が 1 点まで潰れたところが、探していた頂上の位置です。

端も頂上として数える

[1, 2, 3, 4, 5] には、両隣より大きい要素がありません。右端の 5 には右隣が無いからです。この配列では右端を頂上として扱います。[5, 4, 3, 2, 1] なら左端です。

端を頂上に含めないルールにすると、頂上が 1 つも無い配列ができてしまい、必ず見つかるという前提が崩れます。前提が崩れれば、半分を捨てて残ったほうに頂上がある、という言い切りも成り立ちません。片側だけ比べて大きければ頂上、と決めておくことで、どんな配列にも答えがある状態を保っています。

要素が 1 つだけの配列も同じ考え方です。[10] には比べる隣が両側とも無いので、その 1 つがそのまま頂上になります。要素が 2 つの [5, 2] なら、左のほうが大きいので左端が頂上です。

頂上が複数ある配列もあります。そのときはどれか 1 つを返せば正解です。今回のテストは頂上が 1 つに決まる配列だけを使うので、期待値との突き合わせで迷うことはありません。どれを返しても正解になる問題は、テストの作り方まで含めて設計されている、ということです。

1. 計算量は O(log n)
2. 配列の端も片側比較でピーク扱いとする
3. 複数ピークがあっても 1 つ返せば OK (本テストは一意)