162. Find Peak Element - Medium

前往題目

想法

• Binary search，只要注意左右邊界外的數字都比界內數字小

思路

1. 一般的Binary search
2. 每次選中mid看其左右邊相鄰數字
3. 如果左邊比較大那他就有可能是peak，所以往左邊繼續找，因為當前數字比他小；反之右邊也是如此道理
4. 左右邊都沒有比較大的時候就是找到peak了，邊界也是一樣，因為界外數字一定比較小

Code

這題想得有點複雜，其實規律就是哪邊有比較大的就往哪邊找，還有個很重要的條件，相鄰不會相等，所以一定會有peak

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;

            // Left is bigger
            if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) {
                r = mid - 1;
            } else if (mid + 1 < nums.length && nums[mid + 1] > nums[mid]) {
                l = mid + 1;
            } else { // Found peak
                return mid;
            }
        }
        return 0;
    }
}