1. Problem
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed 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] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 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: 5
Explanation: 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
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for all valid i.
2. Solution
I solved this problem like this.
2.1. not O(log n) solution
I just find value confirm all element. It takes at least O(n) time. Although these codes are accepted, they do not satisfy the O(log n) condition.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
for i in range(len(nums)):
if i == len(nums) - 1 or nums[i] > nums[i+1]:
return i
return -1
2.2. O(log n) solution
Other solution is like this.
In order for the time complexity of the array search algorithm problem to satisfy O(log n), Binary Search must be used.
In the end, the peak is to find the largest number in the array. Because it is the largest, it is larger than the numbers on either side.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
h = len(nums)-1
while l<h:
mid = (l+h)//2
if nums[mid]>nums[mid+1]:
h = mid
else:
l = mid+1
return l