LeetCode 162：Find Peak Element——二分查找峰值

題目描述

數組相鄰元素不相等，找任一峰值（大於左右鄰居）下標。想像 nums[-1]=nums[n]=-∞。要求 O(log n)。

二分查找邏輯

檢查中點 mid：

• nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] → 峰值
• nums[mid] < nums[mid+1] → 右側必有峰值，l = mid+1
• nums[mid] < nums[mid-1] → 左側必有峰值，r = mid-1

C++ 實現（迭代版）

int findPeakElement(vector<int>& nums) {
    int l=0, r=nums.size()-1;
    while(l < r-1) {
        int mid = l + (r-l)/2;
        if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
        if(nums[mid] < nums[mid+1]) l = mid+1;
        else r = mid-1;
    }
    return nums[l] > nums[r] ? l : r;
}

遞歸版

int helper(vector<int>& nums, int l, int r) {
    if(l==r) return l;
    if(l==r-1) return nums[l]>nums[r]?l:r;
    int mid = l+(r-l)/2;
    if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]) return mid;
    if(nums[mid] < nums[mid-1]) return helper(nums, l, mid-1);
    return helper(nums, mid+1, r);
}

複雜度

• 時間：O(log n)
• 空間：迭代 O(1)，遞歸 O(log n)