Taking a detour from strings let’s revisit Binary search today!

Q5. Peak index in a Mountain Array

Question link: https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

Thought Process

For every Binary search question there’s a similar concept. You have to find a condition which can be used to distinguish between 2 parts of the search. After that we discard that half of the array which doesn’t satisfy the required conditions.

For the question We observe in the Left of the Peak index that every element is greater than the next one and in the Right of Peak Index, every element is less than the next element.

So if a[i] < a[i+1] that means we are on the Left branch and we’ll shift Start pointer.

Now we ask the question, “Can the mid element be the Peak element?”. Now if the answer yes we need to keep it in out search space and we’ll do Start = MID instead of Mid+1 (Which excludes the mid from the search space).

Clearly the peak doesn’t satisfy the required condition so we’ll do Start=mid+1

Now what about the end pointer? For end pointer the condition is a[i]≥a[i+1], which is satisfied by the peak element so we keep it in the search space. Hence end=mid

We stop when both pointers point to a single element hence start<end is the condition for Loop.

Pseudocode and Test case

TASKs

initialize pointers and start while loop with condition s<e
check if a[i]≥a[i+1] then do end = mid
else do start = mid+1
return either of s or e

Python CODE

def peakIndexInMountainArray(L):
        n = len(L)
        i=0
        j=n-1
        while i<j:
            mid = i + (j-i)//2
            if L[mid] > L[mid+1]:
                j = mid
            else:
                i = mid+1
        return i