動機
二分搜怎麼那麼難搞
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 validi
.
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