找突出

基本款 O(n):

依據邊界為最低點,所以一旦發現下降,表示前一個就是突出,簡化版本:

二分遞迴 O(n):

這題最有趣的地方在於基於邊界都當作是最低,且題目說隨便一個突出都可以。事實上只要滿足中間與其中一側邊,就可以知道另一邊一定有突出。怎麼說呢,舉個例子:

.123.

我們看到 23 就差一點就知道 3 是突出了對吧,儘管右邊仍是 4 也沒有關係,因為邊界無條件是最低。

.1234

歸納出來:

  • left > mid > right => 左邊 一定有 peak

反之

  • left < mid < right => 右邊一定有 peak

另一是:

left > mid < right => 低谷 兩邊一定有 peak

這樣我們可以寫出類似二元搜尋。

最簡化版本 遞迴二元搜尋 O(logn):