⚡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

中文速览与面试要点

山脉数组中查找目标值

(这是一个 交互式问题 )给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。如果不存在这样的下标 index,就请返回 −1。所谓山脉数组,即数组 A 是一个山脉数组的话,需要满足如下条件:① 首先, A.length &gt;= 3 ;② 其次,在 0 &lt; i &lt; A.length − 1 条件下,存在 i 使得 A[0] &lt; A[1] &lt; ... &lt; A[i−1] &lt; A[i] 且 A[i] &gt; A[i+1] &gt; ... &gt; A[A.length − 1] 。你将 不能直接访问 该山脉数组,必须通过 MountainArray 接口来获取数据。约束:3 ≤ mountain_arr.length() ≤ 10^4;0 ≤ target ≤ 10^9;0 ≤ mountain_arr.get(index) ≤ 10^9;最多调用 100 次 get。

核心要点

  • 三步走(标准解) :① 二分找峰值;② 在峰值左侧(升序)二分找 target;③ 若未找到,在峰值右侧(降序)二分找 target。
  • 找峰值 :比较 get(mid) 与 get(mid+1) ——若前者更小则峰在右侧( l = mid + 1 ),否则峰在左侧或就是 mid( r = mid )。
  • 左侧二分(升序) :标准升序二分,找到即返回(因为要求最小下标,左侧优先)。
  • 右侧二分(降序) :注意收缩方向与升序相反—— get(mid) &gt; target 时说明需要更大的值,应 l = mid + 1 。

常见陷阱

  • 右侧降序二分的收缩方向写反 :降序数组中 v &gt; target 时应向右移动(找更小的值),即 l = mid + 1 。写成升序的逻辑会找不到。
  • 先搜右侧再搜左侧 :题目要求返回 最小 下标,因此必须先搜左侧(升序区),左侧找到即返回。
  • 找峰值的区间写成 [0, n−1] :峰不可能是两端(山脉数组定义要求 A.length &gt;= 3 且峰在中间),用 [1, n−2] 可减少边界判断。
  • 超过 100 次 get 调用 :三次二分各需 O(log n) 次 get,n = 10^4 时约 42 次,远低于限制。但若写成线性扫描会超限。
  • 峰值二分的收缩写成 r = mid − 1 : mid 本身可能是峰值,必须写 r = mid 。

参考实现

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

        # ① 二分找峰值(峰顶是唯一满足 A[i] > A[i+1] 的转折点)
        l, r = 1, n - 2
        while l < r:
            mid = (l + r) // 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                l = mid + 1         # 仍在上升 -> 峰在右侧
            else:
                r = mid             # 已在下降 -> 峰在左侧或就是 mid
        peak = l

        # ② 左侧升序区间 [0, peak] 找最小下标
        l, r = 0, peak
        while l <= r:
            mid = (l + r) // 2
            v = mountainArr.get(mid)
            if v == target:
                return mid
            if v < target:
                l = mid + 1
            else:
                r = mid - 1

        # ③ 右侧降序区间 [peak+1, n-1]
        l, r = peak + 1, n - 1
        while l <= r:
            mid = (l + r) // 2
            v = mountainArr.get(mid)
            if v == target:
                return mid
            if v > target:          # 降序:值偏大 -> 需要更大的值 -> 向右
                l = mid + 1
            else:
                r = mid - 1
        return -1