Leetcode: Find peak element
Given an array n of integers, find one peak in O(log*n) time. A peak is defined as a number where the two numbers immediately left and right are strictly less than the number. Numbers outside of the bounds of this array are considered to be smaller.
We can leverage the binary search algorithm to find a peak. This is because we can split the array in two parts and look in the middle. If left and right are smaller, it is a peak, otherwise we move in the direction of the higher element. This allows us to find the peak in log*n steps.
from typing import List
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
m = (l+r)//2
while l < r:
peak = nums[m]
lsm = True if m == 0 or nums[m] > nums[m-1] else False
rsm = True if m == len(nums)-1 or nums[m] > nums[m+1] else False
if lsm and rsm:
return m
if lsm:
l = m+1
else:
r = m
m = (l+r)//2
return m
if __name__ == '__main__':
s = Solution().findPeakElement
print(s([1,2,3,1]), 2)
print(s([5,4,3,2,1,0,-1,-2,-3,-4]), 0)
print(s([0,1,2,3,4,5,6,5,4,3]), 6)