Intuition#

比較 mid 與 mid+1，往較大的方向走一定能找到峰值（因為邊界是 -∞）。

• 因為陣列兩端視為 -∞，只要不在邊界就一定存在峰值
• 如果 nums[mid] < nums[mid+1]，右邊一定有峰值
• 如果 nums[mid] > nums[mid+1]，左邊（含 mid）一定有峰值

Approaches#

1: Linear Scan#

• 概念: 找第一個 nums[i] > nums[i+1] 的位置
• 時間複雜度: O(n)
• 空間複雜度: O(1)

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#

• 概念: 比較 nums[mid] 和 nums[mid+1]，往較大的方向收縮
• 時間複雜度: O(log n)
• 空間複雜度: 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
    }
}

這題不需要陣列有序也能二分！關鍵觀察是邊界為 -∞，所以只要往上坡方向走就一定能找到山頂。

🔑 Takeaways#

• Pattern: 非傳統二分搜尋（不需要有序陣列）
• 關鍵技巧: 二分搜尋不只能用在排序陣列上，只要能找到一個判斷條件將搜尋空間分成兩半即可。這題的判斷條件是「上坡 vs 下坡」