Basic Idea: Binary search
Elaboration:
if an element(not the rightmost one) is smaller than its right neighbor, then there must be a peak element on its right, because the elements on its right is either
1. always increasing > the rightmost element is the peak
2. always decreasing > the leftmost element is the peak
3. first increasing then decreasing > the pivot point is the peak
4. first decreasing then increasing > the leftmost element is the peak
Therefore, we can find the peak only on its right elements( cut the array to half)
The same idea applies to that an element(not the leftmost one) is smaller than its left neighbor.
Conditions:
1. array length is 1 > return the only index
2. array length is 2 > return the bigger number's index
3. array length is bigger than 2 >
(1) find mid, compare it with its left and right neighbors
(2) return mid if nums[mid] greater than both neighbors
(3) take the right half array if nums[mid] smaller than right neighbor
(4) otherwise, take the left half
Run time: O(logn)
Memory: constant
Test cases:
[1]
[1,2]
[2,1]
[1,2,3]
[3,2,1]
[2,1,3]
def findPeakElement(self, nums):
left = 0
right = len(nums)1
# handle condition 3
while left < right1:
mid = (left+right)/2
if nums[mid] > nums[mid+1] and nums[mid] > nums[mid1]:
return mid
if nums[mid] < nums[mid+1]:
left = mid+1
else:
right = mid1
#handle condition 1 and 2
return left if nums[left] >= nums[right] else right
My clean and readable python solution


a little change for the answer, 48ms, beats 82.40%.
class Solution(object): def findPeakElement(self, nums): """ :type nums: List[int] :rtype: int """ left = 0 right = len(nums)1 while left < right: mid = (left+right)/2 if nums[mid] > nums[mid+1] and nums[mid] > nums[mid1]: return mid if nums[mid] < nums[mid+1]: left = mid+1 else: right = mid1 return left

Hi there, I think the answer to your question is that we don't need to find ALL the peaks, nor even the HIGHEST peak.
We just need to find a local peak.
Even if we skip the peak on the right part, in your test case, we will still end up with a local peak on the left park
hope this helps!

@cheffyu Thanks for posting this optimization. It is more closer than to the normal binary search solution that students prepare at college. It is simple and is accepted. Thanks again.