Find in Mountain Array: Triple Binary Search

May 27, 20266 min read

leetcodeproblemhardarraysbinary-search

Find in Mountain Array is a problem that pushes binary search to its limits. You are given an array that goes up to a peak and then comes back down, and you need to find a target value using as few lookups as possible. The array is hidden behind an interface, so you cannot just iterate through it. You get MountainArray.get(k) and MountainArray.length(), and the constraint is that you must minimize calls to get().

This is LeetCode 1095: Find in Mountain Array.

Mountain array [1, 2, 3, 4, 5, 4, 3, 1]. The peak is at index 4 (value 5). Search the ascending half first, then the descending half.

Why this problem matters

At first glance, this looks like a search problem with an odd constraint. But the real challenge is understanding how to decompose a complex search space into parts you can handle with binary search. A mountain array is not sorted globally, but it is made up of two sorted halves: one ascending, one descending. Once you realize that, the approach clicks.

This is a great example of the "reduce and conquer" mindset. Instead of trying to solve the whole problem at once, you break it into smaller subproblems. Find the peak. Search the left half. Search the right half. Each piece is a clean binary search, and together they solve a problem that initially seems unsearchable.

The get() minimization constraint also forces you to think about efficiency in a way that normal array problems do not. You cannot afford extra lookups. Every call matters, and that pressure naturally leads you toward logarithmic solutions.

The key insight

You need three binary searches, run one after another:

Find the peak index. Binary search by comparing arr[mid] to arr[mid + 1]. If arr[mid] is less than arr[mid + 1], the peak is to the right. Otherwise, the peak is at mid or to the left. This is the same logic as Find Peak Element.
Search the ascending half (indices 0 through peak). This portion is sorted in increasing order, so you can run a standard binary search for the target.
Search the descending half (indices peak through end). This portion is sorted in decreasing order, so you run a binary search with the comparisons flipped.

You search the ascending half first because the problem asks for the minimum index. If the target exists in both halves, the ascending half will always have the smaller index.

The solution

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()

        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        lo, hi = peak, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1

The code is three binary searches stacked together. The first finds the peak. The second searches the ascending portion using the normal comparison direction. The third searches the descending portion with the comparison direction reversed: when the value at mid is greater than the target, you go right (because the array is decreasing), and when it is less, you go left.

Always search the ascending half before the descending half. The problem asks for the minimum index where the target appears. If the target exists on both sides of the peak, the ascending side will always have the smaller index, so checking it first lets you return immediately without wasting extra get() calls on the descending half.

Practice binary search patterns with spaced repetition

Visual walkthrough

Step 1: Find the peak with binary search

lo=0, hi=7. mid=3, arr[3]=4, arr[4]=5. Since arr[mid] < arr[mid+1], go right: lo=4. Next: lo=4, hi=7, mid=5, arr[5]=3, arr[6]=1. Since arr[mid] > arr[mid+1], go left: hi=5. Next: lo=4, hi=5, mid=4, arr[4]=5, arr[5]=3. Go left: hi=4. lo equals hi at 4. Peak found at index 4.

Binary search on slope direction. O(log n) calls to find the peak.

Step 2: Search the ascending half [0..4] for target=3

Standard binary search on the sorted ascending portion. lo=0, hi=4. mid=2, arr[2]=3. Target found at index 2.

The ascending half is sorted in increasing order, so normal binary search works.

Step 3: Return 2 (minimum index)

We found target=3 at index 2 in the ascending half. Since we search the ascending half first, this is guaranteed to be the minimum index. No need to check the descending half.

Searching ascending first means we always find the smallest index.

What if the ascending search fails?

If target=3 was not found in [0..4], we would then search the descending half [4..7] using a reversed binary search. In this array, index 5 holds value 3 too, so we would find it there.

The descending half is sorted in decreasing order, so flip the comparison: go left when arr[mid] is too small.

The walkthrough shows the three-phase approach. Finding the peak takes O(log n) calls. Searching each half takes O(log n) calls. In total, you make at most about 3 * log(n) calls to get(), which stays well within the problem's limits.

Complexity analysis

Approach	Time	Space
Triple binary search	O(log n)	O(1)

Time: Each of the three binary searches runs in O(log n). The total is O(log n) since constant factors do not affect big-O. In practice, you make at most about 3 * log2(n) calls to get(), which for n = 10,000 is about 42 calls.

Space: Only a handful of pointer variables (lo, hi, mid, peak). No extra data structures needed.

The building blocks

1. Finding the peak with binary search

This is identical to the Find Peak Element pattern. At each step, compare arr[mid] to arr[mid + 1]:

lo, hi = 0, n - 1
while lo < hi:
    mid = (lo + hi) // 2
    if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
        lo = mid + 1
    else:
        hi = mid
peak = lo

When arr[mid] is less than arr[mid + 1], you are on the ascending slope, so the peak must be to the right. Otherwise, the peak is at mid or to the left. The loop converges when lo == hi, which is exactly the peak index.

2. Binary search on ascending and descending halves

The ascending half is sorted normally, so standard binary search applies. The descending half is sorted in reverse order, so you flip the direction: when arr[mid] is too large, move right instead of left.

lo, hi = peak, n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    val = mountain_arr.get(mid)
    if val == target:
        return mid
    elif val > target:
        lo = mid + 1
    else:
        hi = mid - 1

The only difference from a normal binary search is the elif val > target: lo = mid + 1 line. In a normal ascending search, you would set hi = mid - 1 when the value is too large. Here, because the array is decreasing, larger values are on the left, so you move right to find smaller values.

Edge cases

Target is the peak value. The ascending search will find it at the peak index, or the descending search will. Either way, it works correctly.
Target is not in the array. Both half-searches return nothing, and you return -1.
Target appears only in the descending half. The ascending search comes up empty, and the descending search finds it. The returned index is correct because it is the only occurrence.
Array of length 3 (minimum mountain). The peak is at index 1. The ascending half is [0, 1] and the descending half is [1, 2]. Binary search still works on these tiny ranges.
Target equals the first or last element. Standard binary search handles boundary elements without special logic.

From understanding to recall

The triple binary search pattern for mountain arrays is a building block that shows up beyond this specific problem. Any time you have a search space that is not globally sorted but can be broken into sorted pieces, the same decomposition applies. Rotated sorted arrays, bitonic sequences, and similar structures all respond to this "find the boundary, then search each piece" strategy.

The tricky part is not the code itself. Each binary search is just a few lines. The tricky part is recognizing when to use this pattern and getting the comparison directions right for the descending half. That recognition comes from repetition.

Spaced repetition helps you move from "I understand the solution" to "I can write it from scratch under pressure." Revisiting this problem at increasing intervals cements the pattern so deeply that you will spot it instantly in new contexts, whether it is a different LeetCode problem or a system design scenario where binary search on a non-obvious structure saves the day.

Drill binary search building blocks

Find Peak Element - the same peak-finding binary search used as the first step here
Find Minimum in Rotated Sorted Array - another problem that decomposes a non-sorted array into sorted pieces
Search in Rotated Sorted Array - binary search on a structure that is not globally sorted

If you want a structured way to practice binary search and other algorithm patterns, CodeBricks uses spaced repetition to help you build lasting recall. Each pattern you learn gets reinforced at the right intervals so it sticks when you need it most.

Try CodeBricks free