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
- Three binary searches. First, find the peak: compare
get(mid)withget(mid+1); if increasing, the peak is to the right, otherwise at or left ofmid. - Second, binary search the increasing left side
[0, peak]for the target. - Third, binary search the decreasing right side
[peak, n-1], inverting the comparison. - 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 > targetmeans move right. - Off-by-one in the peak search: the comparison is between
get(mid)andget(mid+1), which requiresmid < n - 1; the loop conditionlo < higuarantees it. - Exceeding the call budget: caching
getresults 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.
🧩 Related Binary Search Problems
中文速览与面试要点
山脉数组中查找目标值
(这是一个 交互式问题 )给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。如果不存在这样的下标 index,就请返回 −1。所谓山脉数组,即数组 A 是一个山脉数组的话,需要满足如下条件:① 首先, A.length >= 3 ;② 其次,在 0 < i < A.length − 1 条件下,存在 i 使得 A[0] < A[1] < ... < A[i−1] < A[i] 且 A[i] > A[i+1] > ... > 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) > target 时说明需要更大的值,应 l = mid + 1 。
常见陷阱
- 右侧降序二分的收缩方向写反 :降序数组中 v > target 时应向右移动(找更小的值),即 l = mid + 1 。写成升序的逻辑会找不到。
- 先搜右侧再搜左侧 :题目要求返回 最小 下标,因此必须先搜左侧(升序区),左侧找到即返回。
- 找峰值的区间写成 [0, n−1] :峰不可能是两端(山脉数组定义要求 A.length >= 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