給定一個整數陣列
nums，找到任意一個峰值元素並回傳其索引。峰值元素是嚴格大於其相鄰元素的元素。假設nums[-1] = nums[n] = -∞。要求O(log n)時間複雜度。
Example:
Input: nums = [1,2,3,1] Output: 2
Intuition
TIP
比較 mid 與 mid+1，往較大的方向走一定能找到峰值（因為邊界是 -∞）。
- 因為陣列兩端視為
-∞，只要不在邊界就一定存在峰值 - 如果
nums[mid] < nums[mid+1]，右邊一定有峰值 - 如果
nums[mid] > nums[mid+1]，左邊（含 mid）一定有峰值
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 找第一個
nums[i] > nums[i+1]的位置 - Time:
O(n) - Space:
O(1)
Linear Scan Code
class Solution {
fun findPeakElement(nums: IntArray): Int {
for (i in 0 until nums.size - 1) {
if (nums[i] > nums[i + 1]) return i
}
return nums.size - 1
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 比較
nums[mid]和nums[mid+1]，往較大的方向收縮 - Time:
O(log n) - Space:
O(1)
class Solution {
fun findPeakElement(nums: IntArray): Int {
var left = 0
var right = nums.size - 1
while (left < right) {
val mid = left + (right - left) / 2
if (nums[mid] < nums[mid + 1]) {
left = mid + 1
} else {
right = mid
}
}
return left
}
}WARNING
這題不需要陣列有序也能二分！關鍵觀察是邊界為 -∞，所以只要往上坡方向走就一定能找到山頂。
🔑 Takeaways
- Pattern: 非傳統二分搜尋（不需要有序陣列）
- Key trick: 二分搜尋不只能用在排序陣列上，只要能找到一個判斷條件將搜尋空間分成兩半即可。這題的判斷條件是「上坡 vs 下坡」