Find a Peak in a Mountain Array

Pattern: Binary Search

Idea:

Variations : Derived from find-peak-element

Important Variation : Find in Mountain Array

---

💻 Code

def find_peak(arr):

    low = 0
    high = len(arr) - 1

	# there would be atleast 2 elements
    while low < high:

        mid = (low + high) // 2
        
		# arr[mid+1] would never give out of bounds exception
        if arr[mid] < arr[mid + 1]: 
        
            low = mid + 1
        else:
            high = mid # search in the left 

    return low

Time complexity - O(log n) Aux. Space complexity - O(1)

---

A Mountain Array looks like:

[1, 3, 5, 7, 6, 4, 2]

There is exactly one peak.

The same Binary Search works:

if arr[mid] < arr[mid + 1]:
    low = mid + 1
else:
    high = mid

This is essentially the same algorithm, but the problem guarantees a mountain structure.

Complexity

• Time: $O(\log n)$

• Auxiliary Space: $O(1)$

---

Important Variation : Find in Mountain Array

This is a more realistic interview follow-up.

Given:

[1, 3, 5, 7, 6, 4, 2]

and target:

6

find its index.

Approach

First find the peak.

Then the array becomes two sorted arrays:

Ascending:

[1, 3, 5, 7]

Descending:

[7, 6, 4, 2]

Perform Binary Search on both sides.

Overall:

$$O(\log n)$$

This is LeetCode 1095 — Find in Mountain Array.

---