LeetCode Find Peak Element：尋找峰值元素

題目描述

峰值元素大於其相鄰元素。給定陣列 num[i] ≠ num[i+1]，找任一峰值索引。想像 num[-1] = num[n] = -∞。要求對數時間複雜度。

二分搜尋思路

檢查中間元素 mid：

• 若 num[mid] > num[mid-1] && num[mid] > num[mid+1] → 峰值，返回。
• 若 num[mid] < num[mid-1] → 左側必有峰值，遞歸左半。
• 若 num[mid] < num[mid+1] → 右側必有峰值，遞歸右半（注意索引偏移）。
• 區間剩 1 或 2 元素直接比較返回。

C++ 實現

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        if (n == 0) return 0;
        if (n == 1) return nums[0] > nums[1] ? 0 : 1;
        int mid = n / 2;
        if (mid - 1 >= 0 && mid + 1 <= n) {
            if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
            if (nums[mid] < nums[mid-1]) {
                vector<int> left(nums.begin(), nums.begin() + mid);
                return findPeakElement(left);
            }
            if (nums[mid] < nums[mid+1]) {
                vector<int> right(nums.begin() + mid, nums.end());
                return mid + findPeakElement(right);
            }
        }
        return -1; // 不應到達
    }
};

複雜度

• 時間：O(log n)，每次區間減半。
• 空間：O(log n) 遞歸棧（可改迭代為 O(1)）。