動機

二分搜怎麼那麼難搞

Problem

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

 

Example 1:

Input: nums = [1,2,3,1]Output: 2Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]Output: 5Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

 

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.

Sol

根據bsearch的best practice，終止條件用左閉右合

那搜尋區間怎麼給? 左邊給0，右邊給多少? 要找的是index，同時考慮到左閉右合，所以應該給len(nums)?

左右兩邊重合時最多會到多少? 就是右邊給的值!!

所以這裡右邊給len(nums)-1

接著去比隔壁的值，決定要留哪一邊，但是是比左邊還是右邊? 左閉右合，所以右邊會多一個，所以比右邊

接著切三個case，

  • 等於: 題目保證不存在
  • 小於: 把左邊拉過來，同時不看這個中點的值，i=mid+1
  • 大於: 把右邊拉過來，同時保留(重合時就是這個值)這個中點的值，j=mid
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        nums = nums 
        i = 0
        j = len(nums)-1
        # len(nums)-1 重合時會等於的值
        while i < j:
            mid = i + (j-i)//2
            print(mid)
            if nums[mid] > nums[mid+1]:
                j = mid # keep it
            else:
                i = mid+1 # drop it
        return i