Find in Mountain Array

Find in Mountain Array takes the plain binary-search trick and bends it over a hill. The array is not sorted top to bottom — it climbs to a single peak, then strictly falls. The win is realizing that each side is sorted on its own, so you can binary-search the array three times instead of scanning it.

The slow way first

The obvious idea is a linear scan: walk every element and compare to the target. That is O(n), and it ignores all the structure the mountain hands us. With a sorted array we would never settle for O(n) — we would binary-search. A mountain is not one sorted array, but it is two of them glued at the peak, so we should still get to O(log n).

The question to ask: can I find the peak quickly, and then binary-search each slope?

The idea: peak, then two halves

Do three binary searches. First, find the peak with a slope search: at mid, compare arr[mid] to arr[mid+1]. If the value is still rising, the peak is to the right; if it is falling, the peak is at mid or to its left. That converges on the summit in O(log n).

Then binary-search the rising side [0..peak] the normal way. If the target is not there, binary-search the falling side [peak+1..n-1] — but with the comparison reversed, because that half decreases.

The key insight: a mountain is two sorted runs. Binary search only needs monotonicity, and each slope has it — you just flip the inequality on the way down.

Walk through it

Step through the animation. Phase 1 slides lo/hi until they meet on the peak at index 2. Phase 2 binary-searches the rising side and fails (8 != 6). Phase 3 searches the falling side with flipped comparisons and lands on index 3, where arr[3] = 6.

Pseudocode

peak = slope-binary-search: at mid, if arr[mid] < arr[mid+1] go right else go left
left = binary-search [0..peak]          # ascending: if arr[mid] < target go right
if arr[left] == target: return left
right = binary-search [peak+1..n-1]     # descending: if arr[mid] > target go right
if arr[right] == target: return right
return -1

The Python solution

def find_in_mountain(arr, target):
    n = len(arr)
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    peak = lo
    lo, hi = 0, peak
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if arr[lo] == target:
        return lo
    lo, hi = peak + 1, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] > target:
            lo = mid + 1
        else:
            hi = mid
    return lo if arr[lo] == target else -1

• The first loop is the slope search: arr[mid] < arr[mid+1] means we are climbing, so the peak is to the right (lo = mid + 1); otherwise the peak is at mid or left (hi = mid). When lo == hi, that index is the peak.
• The second loop is an ordinary ascending binary search over [0..peak]. If arr[mid] < target, the answer is to the right.
• After it, arr[lo] == target tells us whether the rising side held the value; if so we return immediately, which also gives the smallest index since the left side comes first.
• The third loop is a descending binary search. The comparison flips: arr[mid] > target now means we must go right, because larger values sit on the left of a falling run.
• A peak search that touches mid + 1 is safe because the loop maintains lo < hi, so mid is never the last index.

Complexity

Each phase halves its range, so the total is three logarithms, which is still O(log n). We use only a handful of index variables, so the extra space is O(1).

When this pattern shows up

Practice