162_寻找峰值.org

题目

思路

时间复杂度 O(logN) -> 二分查找

不断查找数组的中位数 nums[mid]，如果 nums[mid] < nums[mid+1]，说明 nums[mid] 正处于上升序列，峰值一定出现在 mid 右侧（不含mid）

同理，如果 nums[mid] > nums[mid+1]，说明 mid 可能正好是拐点（峰值）或者 nums[mid] 正处于下降序列，峰值出现在 mid 左侧（含mid）

注意：nums[i] != nums[i+1] 的约束！

code

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:

        if len(nums) == 1: return 0 # badcase

        # 2.递归二分查找
        def binarySearch(nums, i, j):
            if i == j:
                return i
            mid = i + (j - i) // 2
            if mid < len(nums) - 1 and nums[mid] < nums[mid+1]: # nums[mid] 出于上升序列，峰值一定出现在mid右边
                i = mid + 1
            else:
                j = mid
            return binarySearch(nums, i, j)

        return binarySearch(nums, 0, len(nums) - 1)


        # 1.迭代二分查找
        i, j = 0, len(nums) - 1
        while i < j:
            print(i, j)
            mid = i + (j - i) // 2
            if mid < len(nums) and nums[mid] < nums[mid+1]: # nums[mid] 处于上升期，峰值出现在mid右边(可能刚好为mid)
                i = mid + 1
            else:
                j = mid
        return i