前几天刷题群里有朋友卡在 LeetCode 1095 上，说山脉数组的解法绕来绕去，边界条件一多就犯迷糊。这道题其实很有代表性——它是“二分查找变体”里最典型的综合题之一，把“峰值查找”和“两侧有序区间的定向二分”串在一起考，我当年第一次做也踩了不少坑。这篇笔记就把我反复打磨后的完整解法和思考过程写出来，从题意拆解、三次二分的逻辑链条，到边界处理和调试技巧，一次讲透。不管你是刚开始刷二分的入门选手，还是想体系化梳理变体的老手，这篇都有值得参考的地方。
1. 从题目到思路：为什么“山脉数组”不能用普通二分一把梭
1.1 先搞清楚题面到底在说什么
LeetCode 1095 的完整描述是这样的：给你一个“山脉数组”mountainArr，它满足先严格递增后严格递减的性质，也就是说存在一个下标peak，使得mountainArr[0] < mountainArr[1] < ... < mountainArr[peak]，然后从peak之后开始严格递减，直到数组末尾。你要在这个数组里找到目标值target的最小下标，如果不存在就返回 -1。
举个例子，数组[1, 2, 3, 4, 5, 3, 1]，5 就是峰顶，下标是 4。如果target = 3，那么数组里有两个 3，分别在下标 2 和下标 5，题目要求返回最小的那个，也就是 2。
这类数组的“字形”画出来就像一座山，左边上坡、右边下坡，因此得名“山脉数组”。它和普通的“有序数组”最大的区别在于：整个数组不是全局单调的，而是“分段单调”——左半段升序，右半段降序。
很多人拿到这题的第一反应是：那就直接遍历一遍呗，从头扫到尾找 target，遇到就返回。这当然能过，但题目里明确了平台对时间复杂度的限制：最多调用 100 次get方法。也就是说，你必须用 O(log n) 的方案，线性扫描在数据量大的时候大概率超时。这道题的核心考点，就是在非全局有序的数据结构中仍然使用二分查找，这正好是二分思想最需要灵活变通的地方。
1.2 为什么不能直接对整个数组做普通二分
普通二分查找的前提是“数组整体有序”：你取中点mid，比较nums[mid]和target，然后可以放心地丢掉一半区间，因为目标值不可能出现在被丢掉的那一半里。
但山脉数组不行。你在中点拿到一个值mountainArr[mid]，如果它小于 target，你能确定 target 在左边还是右边吗？不能。它可能在左边上坡段，也可能在右边下坡段。如果mountainArr[mid]大于 target，同样没法直接判断该往哪边走。因为数组本身存在“两个方向”，普通二分的“一侧丢弃”策略直接失效。
所以题的破局点在于：既然整个数组不是单调的，那就把它拆成两个单调区间来处理。拆的关键是先找到峰顶位置peak——在峰顶左边，数组严格递增；在峰顶右边，数组严格递减。这样一来，问题从“在一个形态复杂的数组里搜索”，变成了“在两个各自有序的区间里分别搜索”。两次搜索都满足普通二分的前提，问题就简单了。
这里有个隐含的重点值得多说一句：峰顶左边和右边的区间，排序方向不同。左边是升序，可以直接用标准的nums[mid] < target判断；右边是降序，比较逻辑要反过来。很多人正是因为忽略了“降序二分”和“升序二分”的比较方向差异，导致 AC 不了。后面第 2 章我会专门拆这个细节。
1.3 整体解法：三次二分，各司其职
想清楚上面这些，方案就非常清晰了。总体上需要三次二分，分工如下：
- 第一次二分：找到峰顶下标
peak。 - 第二次二分：在左区间
[0, peak]（严格递增）里找 target，找到了直接返回，因为题目要求最小下标，而左边的下标一定更小。 - 第三次二分：如果左区间没找到，再到右区间
[peak+1, n-1]（严格递减）里找 target，找到返回下标，找不到返回 -1。
三次二分各司其职，每次都是 O(log n)，总时间复杂度 O(log n)，完全符合平台“最多调用 100 次 get”的限制。
这个思路本身不难理解，真正容易出问题的是第一和第二、第三次二分各自的边界条件。下面我把每一步掰开揉碎来讲。
2. 第一座山：峰值查找的二分细节
2.1 比较对象的选择：和邻居比，而不是和 target 比
普通二分查找的目标值是一个具体的数，比如 target。但找峰值时，我们的“目标”不是一个数值，而是一个位置——数组中那个“比左边大、比右边也大”的点。
因此，找峰值的二分里，比较的对象不是 target，而是相邻元素。具体做法是：取中点mid，比较mountainArr[mid]和mountainArr[mid + 1]。
- 如果
mountainArr[mid] < mountainArr[mid + 1]，说明当前处于“上坡”阶段，峰顶一定在 mid 的右侧，所以left = mid + 1。 - 如果
mountainArr[mid] > mountainArr[mid + 1]，说明当前处于“下坡”阶段，峰顶是 mid 或者在 mid 的左侧，所以right = mid。
这里的关键是：当mountainArr[mid] > mountainArr[mid + 1]时，不能直接把right更新为mid - 1，而要保留mid。因为mid本身可能就是峰顶。你把峰顶丢了，后面就永远找不到它了。
2.2 为什么终止条件要写成left < right
峰值查找的二分，循环条件一般是while (left < right)，而不是普通二分常用的while (left <= right)。原因和上面说的“保留 mid”直接相关。
当区间收窄到只剩一个元素时——也就是left == right——这个位置就是我们要的峰顶。此时如果继续进入循环，mid会和left、right相等，代码可能陷入死循环或者越界。所以循环条件设为left < right，循环结束时left == right，这个位置就是峰顶，直接返回即可。
这个写法和标准二分查找的“闭区间三要素”有一个明显差别：标准写法里，left == right时还需要再判断一次nums[mid] == target，但峰值查找不需要，因为我们要的是“极值位置”，区间收缩到一点时，那个点必然满足峰顶的性质（前提是数组结构符合山脉定义）。
注意：找峰值时，为什么只比较
mid和mid + 1，不需要比较mid和mid - 1？因为山脉数组严格递增后严格递减，相邻元素不会相等。比较mid和mid + 1只需要保证mid + 1不越界，而mid在left < right的前提下，mid + 1最大是right，不会等于n。如果改成比较mid - 1，则在left == 0时可能访问-1，还需要额外的越界判断，反而麻烦。
2.3 峰值二分的完整实现
用 Python 写出来就是这样：
def find_peak(mountainArr): left, right = 0, mountainArr.length() - 1 while left < right: mid = left + (right - left) // 2 if mountainArr.get(mid) < mountainArr.get(mid + 1): left = mid + 1 else: right = mid return left这里我特意用了left + (right - left) // 2而不是(left + right) // 2，两个写法在数学上等价，但前者可以避免left + right在极端情况下溢出。虽然 LeetCode 平台一般不会把数组长度设到溢出级别，但这是一个好习惯，建议所有二分都这么写。
这段代码里最反直觉的地方在else分支：为什么mountainArr[mid] > mountainArr[mid + 1]时，right = mid，而不是更“自然地”写成right = mid - 1？
还是那句话：mid可能就是峰顶。比如数组[1, 3, 2]，第一次循环mid = 1，arr[1] = 3 > arr[2] = 2，如果right变成 0，那峰顶 1 就直接被排除在搜索区间之外了，后面啥也找不到。保留mid，区间从[0, 2]收窄到[0, 1]，再下一轮mid = 0，arr[0] = 1 < arr[1] = 3，left = 1，此时left == right == 1，退出循环，返回 1，正确。
3. 左右开弓：两个有序区间的定向二分
3.1 左区间：标准升序二分的直接套用
拿到峰顶peak之后，左区间[0, peak]是一个严格递增的数组。搜索 target 就是一个标准的升序二分查找，凡是刷过几道二分题的人都很熟悉：
def search_increasing(mountainArr, target, left, right): while left <= right: mid = left + (right - left) // 2 val = mountainArr.get(mid) if val == target: return mid elif val < target: left = mid + 1 else: right = mid - 1 return -1这里用while (left <= right)是恰当的，因为我们要精确找 target，区间为空时即left > right时停止。找到就返回下标，没找到返回 -1。
有一个细节值得留意：左区间搜索的终止条件和峰值查找不一样，这里用的是“闭区间+等号”，因为搜的是一个具体值，不是极值位置。两种二分形态的使用场景不同，不能混用。
3.2 右区间：降序二分的比较方向反转
右区间[peak + 1, n-1]是严格递减的。很多人在这里写错，是因为“惯性思维”把升序二分的写法原封不动搬过来了。但降序区间里，数组的趋势反了：数值越大，下标反而越小。
所以比较逻辑要反转：
def search_decreasing(mountainArr, target, left, right): while left <= right: mid = left + (right - left) // 2 val = mountainArr.get(mid) if val == target: return mid elif val < target: right = mid - 1 # 注意这里，降序时小的值在右边 else: left = mid + 1 # 大的值在左边 return -1逐行解释一下这个反转：
- 在降序数组中，
mid的值如果小于 target，说明 target 所在的区域是“值更大的方向”，也就是mid的左侧，所以要收缩右边界right = mid - 1。 - 如果
mid的值大于 target，说明 target 在“值更小的方向”，也就是右边，所以要收缩左边界left = mid + 1。
升序和降序两个函数只有两行left/right的更新写反了，但这就是二分里最容易阴沟翻船的地方。我自己也曾经在右区间用升序逻辑，结果测试用例里目标值在右区间时永远返回 -1，排查半天才意识到是方向搞错了。
3.3 主流程：先左后右，天然满足“最小下标”
最后把三次二分串起来：
class Solution: def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int: n = mountainArr.length() # 第一次二分：找峰顶 left, right = 0, n - 1 while left < right: mid = left + (right - left) // 2 if mountainArr.get(mid) < mountainArr.get(mid + 1): left = mid + 1 else: right = mid peak = left # 第二次二分：左区间（升序） idx = self._binary_search_increasing(mountainArr, target, 0, peak) if idx != -1: return idx # 第三次二分：右区间（降序） return self._binary_search_decreasing(mountainArr, target, peak + 1, n - 1)为什么先搜左区间而不是右区间？因为题目要的是最小下标。左区间的所有下标都小于右区间的所有下标，所以只要左区间找到了，它一定比任何右区间的答案都小，直接返回即可。如果左区间找不到，才去右区间找。
这里还有一个边界上的细节：右区间的搜索起点是peak + 1而不是peak。因为peak已经在左区间搜索范围内，左区间已经把peak这个位置检查过了。重复检查没有意义，而且从peak + 1开始，右区间的严格递减性质更纯粹，避免边界歧义。
4. 调试实录：我在这道题上踩过的四个坑
4.1 坑一：峰值查找的区间收缩把峰顶丢了
一开始写峰值二分时，我把else分支写成了right = mid - 1，被平台一个普通用例直接打脸：[1, 3, 2]找目标值 3，返回-1。
原因前面已经分析过，mid是峰顶时被排除，搜索区间根本没有包含正确答案。这类 bug 很隐蔽，因为不是每个用例都会触发，只有当峰顶恰好落在mid位置上才会暴露。排查方法也很简单：把每次循环的left、right、mid打印出来，跟踪区间变化，立刻就能看到峰顶被跳过的过程。
4.2 坑二：右区间用了升序二分的比较逻辑
在search_decreasing里，我一开始写的是标准升序逻辑：val < target时left = mid + 1，导致降序区间的目标值永远搜不到。
这个坑的教训是：二分查找的“骨架”只是模板，真正决定对错的是“区间收缩方向和数组单调方向是否匹配”。写降序二分时，最好在纸上先画一个简单的递减数组比如[5, 4, 3, 2, 1]，手动走一遍target = 2的查找过程，确认哪边该缩。手动模拟两步，比事后调试省时间得多。
举例：arr = [5, 4, 3, 2, 1], target = 2 初始 left=0, right=4, mid=2, arr[2]=3 > 2 降序逻辑：arr[mid] > target, 说明 target 在右侧，left = mid + 1 = 3 区间 [3,4], mid=3, arr[3]=2 == 2，返回 3 如果用了升序逻辑：arr[mid] > target, right = mid - 1 = 1, target 就被丢在区间外了4.3 坑三：混淆了“峰值查找”和“值查找”的循环终止条件
峰值查找用while left < right，返回的是left；值查找用while left <= right，返回的是找到的下标或者 -1。这两个条件我一开始没分清，在峰值查找里用了<=，结果在left == right时还会再算一次mid，在某些用例里陷入死循环。
区分方法非常直接：你是不是在找一个“位置性质”？如果是，比如“峰顶”“第一个坏版本”“旋转数组的最小值”，循环条件是left < right，区间收敛到一点就是答案；如果你是在找一个具体的相等值，那循环条件是left <= right，因为相等时就要 return，区间为空就是没找到。把这个问题想明白了，二分的终止条件就不会再混。
4.4 坑四：重复调用get导致计数超标
LeetCode 1095 的MountainArray接口有调用次数限制，最多 100 次。我第一版代码里，峰值查找和两次值查找之间互相重叠，导致同一个下标被重复get，测试用例多一点就直接超限。
解决办法是：函数调用时尽可能把相同的get结果存到局部变量里，比如上面代码里的val = mountainArr.get(mid)，整个循环体内只用这一句，后续比较都用val而不是再次调用get。虽然每次二分只有 O(log n) 次get，三次加起来远小于 100，但代码规范一点，既省调用次数，也让逻辑更清晰。
另外，写题的时候我还额外加了一点防御性设计：值查找的前置判断。在进入二分前，先检查target是否小于左区间的最小值arr[0]或大于左区间的最大值arr[peak]，如果不在范围内就直接跳过左区间二分。这个剪枝不是必须的，但可以减少无效的调用次数，也是一种好习惯。
5. 从 1095 延伸开：这题背后的二分变体体系
5.1 和旋转排序数组的对比
如果你刷过 LeetCode 33“搜索旋转排序数组”，会发现它和 1095 有某种相似感——都是“整体无序，但分段有序”。旋转数组是由一个升序数组在某个点切割后交换顺序得到的，比如[4, 5, 6, 7, 0, 1, 2]，它也是“两段有序”，只是有序段的方向都是升序，而山脉数组两段方向相反。
两类题的核心思想完全一致：先通过某种方式找到“分界点”，再在分界后的有序区间上做普通二分。旋转数组的分界点是“最小值位置”，山脉数组的分界点是“峰顶”。找到了分界点，整个问题就被化解为最基础的二分查找，难度瞬间下降。
所以 1095 的价值不只是它本身，而是它让你理解了“分界点+定向二分”这个组合套路。后面做搜索旋转数组、寻找峰值、寻找旋转数组最小值时，很多代码结构都是互通的。刷一道题，打通一类题，这才是刷题效率最高的方式。
5.2 二分查找的本质：单调性与决策方向
做题多了你会发现，普通二分、找峰值、找旋转点、甚至是在有序矩阵里搜索，这些问题的共性都是利用某种单调性质，排除掉不可能包含答案的区间。
- 普通二分里，答案是一次比较后直接排除一半。
- 找峰值里，一次比较
arr[mid]和arr[mid+1]可以确定“峰顶在上坡方向还是下坡方向”，从而排除另一半。 - 旋转数组找最小值里，比较
arr[mid]和arr[right]可以确定“最小值在左半还是右半”。
抓住这个本质，你不需要背“模板”，只需要在每一步都问自己：我做这个比较，能不能严格排除掉一部分区间？如果能，那这个方向就是对的；如果不能，说明比较对象选错了。
这也是我在刷题过程中最大的体会：二分不是“会背模板”就能解决的题型，而是一种基于单调性的思维决策过程。题目一变，比较对象、区间收缩方向、终止条件都要跟着变，只有理解了“为什么”，才能以不变应万变。
5.3 如果面试官追问：还能怎么优化
1095 本身的解法已经是 O(log n)，时间复杂度上没有再优化的空间了。但面试官可能会问一些延伸问题，比如：
- 如果山脉数组中存在多个相等的 target，你还能保证返回最小下标吗？这个题本身的“先左后右”顺序已经保证了，但你要能说清楚为什么。
- 如果数组不满足“严格递增后严格递减”，而是允许平台段（相等元素），你的峰值查找还成立吗？答案是可能需要调整，因为
arr[mid] == arr[mid+1]时你无法判断方向。 - 如果只允许最多调用 k 次
get，你的算法是否满足？可以估算一下：峰值查找大约log2(n)次，两次值查找最多各log2(n)次，总共约3 * log2(n)次。对n <= 10000来说，大约 42 次左右，远小于 100 的限制。
能回答上这些追问，说明你是真的理解了这题，而不是背了个答案。
6. 自己动手：一套可复用的速查清单
刷完 1095，我记得最牢的是一套“山脉数组二分自查清单”，这里分享给你：
- 第一步永远先找峰顶。没有峰顶位置，后面两个区间搜索都无从谈起。
- 峰值查找用
left < right，区间收缩到一点就是峰值；收缩时right = mid而不是right = mid - 1。 - 左区间升序二分，
val < target时left = mid + 1。 - 右区间降序二分，
val < target时right = mid - 1。方向别写反。 - 先搜左区间再搜右区间，因为题目要最小下标。
- 所有
mid计算都用left + (right - left) // 2。 - 每次
get结果存局部变量，不要重复调用。 - 如果你没法一眼看出方向，在纸上画一个
[1,2,3,4,5,3,1]的图，把每次二分区间收窄的过程标出来，跑一轮你就有感觉了。
这套清单不只是为 1095 服务的。后面刷 162 寻找峰值、852 山脉数组的峰顶索引、33 搜索旋转排序数组时，我都反复用这同一套思维框架，几乎不需要额外适应，直接套上就能写。二分的题目看似很多，真正核心的骨架其实就这么几个，把一道综合题吃透，远胜过盲目刷十道简单题。
最后再分享一个个人的小习惯：每道二分的题 AC 之后，我都会故意把“升序/降序”改错一次，看自己能不能通过样例发现正确方向。这个“主动制造错误再修正”的练习法，帮我建立了对二分方向更敏感的直觉，比连续刷同类型十道题的效果还要好。你也可以试试。
