A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
My Solution
Since the problem allows a local maxima to be a valid peak (return the index to any one of the peaks is fine), we don’t need to look for the max of all the numbers. The most naive approach is to use linear searching, return the first local maxima by detecting if current number is less then the previous one. If we have reached the end of the list and the “decrease” is not detected, then we can just simply return the last element which is local maxima in this case. The code should be straight forward as below, and the time complexity is O(n).
def find_peak_element(nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1,len(nums)):
if nums[i] < nums[i-1]:
return i-1
return len(nums)-1
We can optimize this using the classic algorithm binary search that would reach O(log n) complexity. Again we only need to find local maxima, the code should be typical binary search implementation but we should be careful not to access outbound element in the array by not putting ‘=’ sign in the while loop condition, since we iterate the mid pointer and mid+1.
def find_peak_element(nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums)-1
while l < r:
mid = (l+r)/2
if nums[mid] < nums[mid+1]:
l = mid+1
else:
r = mid
return l
Giri Kuncoro 