162. Find Peak Element

Description:

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.

 

'''
[1] linear search - Time Limit Exceeded)

idea::
find peak element from index 0

code::
for i in range(1,len(nums)-1):
    if nums[i]>nums[i-1] and nums[i]>nums[i+1]:
        return i
return None

-T/C: O(n)
-S/C: O(1)
'''

'''
[2] Binary Search)

idea::
in problem, require O(logn) to solve it. naturally, Binary search algorithm will be come up with.

then, consider mid point.
1) ascending 2) decreasing 3) peak 4) valley(smallest)
 => case 1: peak will lie on right part
 => case 2: peak will lie on left part
 => case 3: return it!
 => case 4: both parts will have peak!
then, can write code(recursively or iteratively)

 code::
(below)
 
-T/C: O(logn)
-S/C: O(1)
'''

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left,right= 0, len(nums)-1
        
        while left<=right:
            if left==right:
                break
            
            mid=(left+right)//2
            if mid+1<len(nums) and nums[mid]<nums[mid+1]:
                left=mid+1
            else:
                right=mid
            
        return left