题解 | #寻找峰值#

标签：二分法

• 递归解法（不建议）

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        elif len(nums) == 2:
            if nums[1] > nums[0]:
                return 1
            else:
                return 0
        
        for i in range(1, len(nums) - 2):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                print(i)
                return i
        
        if nums[0] > nums[len(nums) - 1]:
            return 0
        else:
            return len(nums) - 1

• 二分法（建议）

参照： https://blog.nowcoder.net/n/eafbb55131ec4e7f83360ed84c7ad911

核心逻辑：

//右边是往下，不一定有坡峰
if(nums[mid] > nums[mid + 1])
    right = mid;
//右边是往上，一定能找到波峰
else
    left = mid + 1;

完整代码：

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left