Find Peak Element
題目描述
給定一個整數陣列 nums，找到一個峰值元素（比左右鄰居都大）的索引。陣列可能有多個峰值，回傳任意一個即可。假設 nums[-1] = nums[n] = -∞。
輸入：nums = [1,2,3,1]
輸出：2
解釋：nums[2] = 3 是峰值
輸入：nums = [1,2,1,3,5,6,4]
輸出：5（或 1，任意峰值皆可）
解題思路
設定範圍
left = 0, right = n - 1，搜尋範圍包含整個陣列
取中間值
mid = left + (right - left) / 2，注意 mid 永遠不會等於 right（因為整數除法向下取整）
比較右鄰居
比較 nums[mid] 和 nums[mid+1]：若 nums[mid] 較小代表上坡，峰值在右側；否則下坡或已是峰值
縮小範圍
上坡 → left = mid + 1（mid 不可能是峰值）；下坡 → right = mid（mid 可能是峰值所以保留）
left == right
兩指標收斂到同一位置，該位置就是峰值——因為我們始終往上坡方向走，最終一定停在峰頂
程式碼
C#
public class Solution {
public int FindPeakElement(int[] nums) {
int left = 0, right = nums.Length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // 上坡，峰值在右側
} else {
right = mid; // 下坡或相等，峰值在左側（含 mid）
}
}
return left;
}
}TypeScript
function findPeakElement(nums: number[]): number {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // 上坡，往右找
} else {
right = mid; // 下坡，往左找（含 mid）
}
}
return left;
}Python
def findPeakElement(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1 # 上坡，峰值在右邊
else:
right = mid # 下坡，峰值在左邊或就是 mid
return left複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(log n) | O(1) |
- Time：每次迭代砍掉一半搜尋範圍，最多迭代 log2(n) 次
- Space：只用了常數個指標變數
圖解
圖表展示了二分搜尋的方向判斷邏輯：比較 mid 和 mid+1 決定坡度方向。 因為陣列兩端是 -∞，往上坡方向走一定會遇到峰值（不可能一路上坡到負無窮）。
進階觀點
💡面試追問
Q: 為什麼這題能用 Binary Search？陣列又沒有排序。
A: 關鍵前提是 nums[-1] = nums[n] = -∞。這保證了搜尋空間的兩端都是「谷底」，所以只要偵測到上坡方向（nums[mid] < nums[mid+1]），往那個方向走一定會在抵達邊界前遇到下坡，從而找到峰值。這不需要全域有序，只需要「局部單調性保證峰值存在」。
Q: 如果陣列嚴格遞增怎麼辦？ A: 每次都判定為上坡，left 持續右移，最終 left = right = n-1，最後一個元素就是峰值（因為右邊是 -∞）。嚴格遞減同理，left 不動而 right 一路左移，最終峰值是第一個元素。
Q: 2D 版本（Find Peak Element II, LC 1901）怎麼解？ A: 對中間列找該列的最大值，再比較它和相鄰列對應位置的值，決定往左半還是右半搜尋。時間 O(m log n) 或 O(n log m)，核心思路仍是「往上坡方向走一定能找到峰值」。
邊界情況
- 陣列只有一個元素：left = right = 0 直接返回 0，因為它左右都是 -∞ 所以是峰值
- 陣列只有兩個元素：一次比較就能確定哪個是峰值
- 存在多個峰值：Binary Search 不保證找到全域最大值，只保證找到某一個局部峰值（題目只要求回傳任一個）
理解測驗
🤔 為什麼 nums[mid] < nums[mid+1] 時要往右移動？
🤔 為什麼用 left < right 而不是 left <= right？