⚡Flashcard Drill➔
NeetCode #300LC-1095HardBinary SearchNC 250
← Back to All Problems

#300 · #1095 · Find in Mountain Array(山脉数组中查找目标值)

📌 Problem Statement & Constraints

This is an interactive problem. A MountainArray is strictly increasing then strictly decreasing. Given a target, return the minimum index where it appears, or -1. You may call get(k) at most 100 times, and length() once. Constraints: 3 <= length <= 10^4, 0 <= target <= 10^9.

💡 Core Algorithmic Approaches

  1. Three binary searches. First, find the peak: compare get(mid) with get(mid+1); if increasing, the peak is to the right, otherwise at or left of mid.
  2. Second, binary search the increasing left side [0, peak] for the target.
  3. Third, binary search the decreasing right side [peak, n-1], inverting the comparison.
  4. Searching the left side first is required because the problem asks for the minimum index.

💻 Benchmark Python3 Implementation

class Solution:
    def findInMountainArray(self, target: int, mountainArr: "MountainArray") -> int:
        n = mountainArr.length()
        # 1) find the peak
        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                lo = mid + 1           # still ascending
            else:
                hi = mid
        peak = lo

        # 2) ascending side [0, peak]
        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            v = mountainArr.get(mid)
            if v == target:
                return mid             # minimum index by construction
            if v < target:
                lo = mid + 1
            else:
                hi = mid - 1

        # 3) descending side [peak, n-1]
        lo, hi = peak, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            v = mountainArr.get(mid)
            if v == target:
                return mid
            if v > target:             # descending -> go right for smaller values
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) calls to get: three binary searches, about 3 * log2(10^4) ≈ 42 calls, within the 100-call budget.
💾 Space Complexity
O(1): a few indices.

⚠️ Interview Pitfalls & Follow-ups

  • Searching the descending side first: the answer must be the minimum index, so the ascending side must be checked first.
  • Inverting the comparison on the descending side: there, smaller values are to the right, so v > target means move right.
  • Off-by-one in the peak search: the comparison is between get(mid) and get(mid+1), which requires mid < n - 1; the loop condition lo < hi guarantees it.
  • Exceeding the call budget: caching get results or using a helper is wise if the budget were tighter; three binary searches fit comfortably here.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems