Leetcode 162. Find Peak Element

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 -231 <= nums[i] <= 231–1 nums[i] != nums[i + 1] for all valid i.

My First wrong approach

Earlier I was thinking to move mid based on left pointer element and right pointer element. But this will give more ambiguity. Instead of this, we need to do shifting by checking the neighbourhood condition.

My Approach:

If you see in this image then when there is increasing steep that is M<M+1 In that case the peak element will be available if we do left = mid+1

Thereafter, if we see this image then when there is decreasing steeply that is arrr[m-1] > arr[m] In this case we do the r = m-1

By this way we can get the peak element

When we reach the peak element we will stop the iteration. the condition for this will be

if nums[m-1]<nums[m]>nums[m+1]:
    return m

Thus based on the conditions we can get the code as follows:

        l = 0
        r = len(nums)-1

        if len(nums)==1:
            return 0
        
        while l<r-1:
            m = (l+r)//2
            if nums[m-1]<nums[m]>nums[m+1]:
                return m
            if nums[m-1]<nums[m]<nums[m+1]:
                l = m+1
            else:
                r = m-1

Now there are the two cases when we have two elements or 1 element
[1,2] [2,1] → then this is creating ambiguity

Moreover, when [1] → again ambiguity

So we add one last condition that

return l if nums[l] >= nums[r] else r