筆記: 【演算法新手村】[初階]筆記03 - 二分練習題

題目翻譯

所謂的峰值元素（Peak Element），是指一個其值嚴格大於左右鄰居的元素。
給定一個下標從 0 開始的整數陣列 nums，請找到一個峰值元素並回傳其索引值（index）。如果陣列中包含多個峰值，回傳任何一個峰值的索引即可。

你可以假設 nums[-1] = nums[n] = -∞ 。換句話說，陣列邊界外的鄰居總是被視為比陣列內的元素小。
你必須撰寫一個時間複雜度為 O(log n) 的演算法。

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] 對所有有效的 i

解題思路

看到複雜度看看可不可以二分：
因為題目保證 nums[i] ≠ nums[i+1]，且邊界外視為負無窮大。
這意味著只要數列在上升，往右走一定能遇到山峰（或是邊界）；反之亦然(因為那怕全部數值都是遞增的，因為邊界外是無窮小，最後一個元素依然符合峰值的定義(同時大於兩邊)，全遞減道理相同)，也就是說這題保證一定會有所謂的峰值出現。

綜上所述，可以二分

當然，有一些特殊情況是我們可以先解決掉的：

• 如果長度為1，唯一的元素即是答案
• 檢查第一個或是最後一個元素是不是答案

需要注意的是先排除這些條件後進行二分時索引可以往內縮1(即 l = 1 , r = n-2 )，因為我們確認過邊緣兩個位置了，所以不需要重複檢查。排除前面的條件後，代表峰值一定在中間出現(因為既然兩邊不是峰值就代表剛開始是遞增，卻以遞減結束，不難得出中間必有峰值的結論)，因此才進行二分。

二分時，有幾點要明白，峰值是同時比兩邊大，也就是我們要對兩邊進行檢查，這邊以先檢查右邊為例，如果當前的右邊元素較大(代表當前處於遞增區間)就代表峰值在右邊(因為是以遞減區間結束)，所以往右搜；如果當前左邊元素較大(代表當前遞減區間)就代表峰值在左邊(因為是以遞增區間開始)，所以往左搜。
如果都不是那就代表同時比兩邊大，直接返回即可。

要記得一點：

一定要確認有答案才進行二分

程式碼實作 (C++)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)return 0;
        if(nums[0] > nums[1]) return 0;
        else if(nums[n-1] > nums[n-2]) return n-1;

        int l = 1 , r = n-2 , m = -1;
        int ans = -1;
        while(l <= r)
        {
            m = (l+r)/2;
            if(nums[m] < nums[m+1]){
                l = m + 1;
            }
            else if(nums[m] < nums[m-1]){
                r = m-1;
            }
            else{
                ans = m;
                break;
            }
        }
        return ans;
    }
};

C的code幾乎相同，略。