1. 这道题真正卡人的地方不是二分而是那个接口限制我第一次在题库里看到 MountainArray 这个接口的时候确实愣了一下。题目不给你完整的数组只给你一个黑盒般的接口能调用length()拿长度能通过get(i)拿某个下标的值还额外加了一条硬性限制整个查找过程中get()最多只能调 100 次。数组长度最大是 10000这意味着你不可能从头到尾扫描一遍——老老实实遍历到一半调用次数就爆了。这个设计挺刁钻也挺高明。它逼着你换一个思路去想问题在不看全量数据的前提下能不能利用数组自身的结构特征把查找效率做到对数级别山脉数组的定义本身很单纯长度至少为 3存在一个峰值下标peak使得左半段[0, peak]严格递增右半段[peak, n-1]严格递减。注意严格两个字意味着不会出现相邻元素相等的情况。别小看这个性质后面找峰值时你会发现正是严格保证了各种二分推导能够站得住脚。我见过不少人的第一反应是先遍历找到峰值再在两边做二分这种思路方向是对的但第一步就违背了接口限制。峰值的查找也必须在对数时间内完成整体方案得是三次二分嵌套第一次二分在[0, n-1]区间内定位峰值位置第二次二分在递增段[0, peak]内查找目标值第三次二分在递减段[peak, n-1]内查找目标值。每一轮都是 O(log n)总操作次数加一起也就四五十次距离 100 次的限制线还很宽松。但为什么三次二分就是这个题的最优解峰值凭什么能用二分去定位左右两侧的二分模板又差在哪里这些细节我打算一个个拆开讲顺便把这道题里真正值得记录的坑都摊开说清楚。2. 峰值查找为什么能二分相邻比较背后的单调性判断很多人第一反应是找峰值还不简单遍历一遍找到第一个满足arr[i] arr[i1]的位置不就行了问题是那样是 O(n)接口不允许。也有同学想到三分查找每次取两个中间点mid1、mid2做比较也可以把区间收敛到对数级别。三分确实可行但它在离散数组上迭代结束时还需要额外处理边界而且每次迭代要调用两次get()代码写起来绕逻辑反而不直观。峰值查找其实有更直接的二分思路。核心判断只有一句话——比较mid和mid1位置的元素大小就能确定峰值在mid的哪一侧。自己推一遍就清楚了如果arr[mid] arr[mid1]说明当前位置正处于上坡阶段。数组从这个点往后还在变大那么峰值一定在mid的右侧因为整个数组只有一座山你现在在山峰的左坡上继续往右走才有可能到顶。此时收缩左边界l mid 1。如果arr[mid] arr[mid1]说明当前位置要么是峰值本身要么已经处于下坡阶段。峰值不可能在mid右侧的递减段里所以收缩右边界r mid。这个判断只用到了两个相邻元素的大小关系不需要任何其他信息。它之所以成立本质上是利用了严格递增后严格递减这个单峰结构。单峰函数有个特点任意相邻位置的大小比较都能告诉我们当前是处在峰的左侧还是右侧信息量足够完成二分区间的决策。用生活化的类比来说就像你在爬一座只有一座山顶的山。你闭着眼睛往前走只要摸摸脚下的路是往上还是往下就知道山顶在哪个方向。不需要知道整座山长什么样也不需要知道自己离山顶还有多远一路顺着往上就继续走、往下就回头的规则就能摸到山顶。对比三分查找三分每次需要比较两个点当mid2 mid1 1这种极端情况出现时还要小心区间收缩会不会死循环。而用相邻比较法实现的二分代码更短边界条件也更干净。我个人的建议是峰值查找就用这种和下一个位置比大小的写法不要搞花活。3. 第一次二分峰值查找的具体实现与三个边界细节峰值查找的代码框架不长但每个细节都值得抠一抠int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (mountainArr.get(mid) mountainArr.get(mid 1)) { l mid 1; } else { r mid; } } int peak l;第一个细节为什么要拿mid和mid1比而不是mid和mid-1比理论上两种比较都能推导出方向但和mid-1比较时如果mid 0就会越界需要额外做防御判断并且中位数的取法要改成上取整否则容易陷入死循环。而和mid1比较循环条件l r保证了mid一定小于r初始时r n - 1所以mid 1最大也就是n - 1天然不会越界。这种实现避免了最麻烦的一个边界问题。第二个细节为什么循环条件是l r而不是l r因为我们要找的是一个确定存在的位置当区间收缩到只剩一个元素时那个元素就是峰值候选。l r保证循环结束时l r直接返回即可。如果用l r最后一轮会出现左右边界交错的情况你就得额外维护一个变量记录上一次的候选答案代码会变长而且容易出错。第三个细节中位数取下整mid l (r - l) / 2配合arr[mid] arr[mid1]则l mid 1这个分支绝不会死循环。因为当下取整且l r时mid严格小于rmid 1合法且l mid 1一定比原来的l至少大 1区间在持续收缩。你可以试试把中位数改成上取整再跑一遍同样的分支逻辑很快就会发现mid 1可能一直等于r循环永远跳不出去。这些都是二分的基本功但正因太基础翻车率反而最高。还有一个在实际刷题中容易忽略的点峰值查找过程中访问过的下标后面左右二分时大概率还会再访问到。比如峰值附近的位置左段二分可能查右段二分也可能查。如果不对get()的结果做缓存调用次数可能逼近上限。这个我在后面单独讲。峰值查找做完之后可以顺手验证一件事如果peak 0或peak n-1说明输入不是合法的山脉数组。但题目保证了输入一定是合法的山脉数组所以代码里不需要加防御分支。不过我还是建议在注释里写明这个隐含前提免得后来读代码的人在这里多想。4. 第二、三次二分递增段和递减段唯一的区别就在比较符号定位到峰值之后整个数组就被分成了两段左段[0, peak]严格递增右段[peak, n-1]严格递减。左段可以直接套标准的递增二分模板。右段则需要反着来——当arr[mid]大于target时要往右半段找当arr[mid]小于target时要往左半段找。原因也很直白递减序列越往右值越小中点的值比目标值大说明目标值在中点右侧更小的那一堆里中点的值比目标值小说明目标值在中点左侧更大的那一堆里。左段二分代码int l 0, r peak; while (l r) { int mid l (r - l) / 2; int val mountainArr.get(mid); if (val target) return mid; if (val target) { l mid 1; } else { r mid - 1; } }右段二分代码int l peak, r n - 1; while (l r) { int mid l (r - l) / 2; int val mountainArr.get(mid); if (val target) return mid; if (val target) { l mid 1; } else { r mid - 1; } }对比这两段代码唯一的差别就是val和target的比较符号反过来了。左段是val target时移动左边界右段是val target时移动左边界。很多人第一次写右段二分时容易照着左段模板惯性地写结果目标值明明在右段却永远返回 -1。我建议右段的二分代码单独复制一份再改不要在原模板上看着改这样不容易改漏。关于右段的起始下标我推荐写成peak 1而不是peak。因为peak位置在左段二分里已经查过了既然走到右段分支说明左段没命中peak位置的值不等于target不需要再查一次。虽然只省一次get()但能省则省的习惯在接口受限的场景下很值得养成。另外注意查找顺序题目要求返回最靠前的下标。所以要先做左段二分命中就直接返回只有左段返回 -1 了才去做右段二分。右段如果也返回 -1最终答案就是 -1。这个先后顺序不能反反了可能会返回一个更大下标即使值相同也属于错解。关于是否要写一个带方向标志位的统一二分函数我有自己的看法。有人为了省代码把递增、递减合并成一个函数传入isIncreasing标志位在比较逻辑里做方向判断。这样做确实能减少重复代码但牺牲了可读性面试讲解时也容易绕晕自己。我的习惯是写两个独立的二分方法方法名直接叫binarySearchLeft和binarySearchRight一个对应递增段一个对应递减段哪怕多一点重复也值得。真实工程里可读性永远比少写几行更重要刷题时养成的代码风格会影响你后续的工程习惯。5. 100次 get 的限制缓存设计、计数统计与鲁棒性细节接口限制是最多调用 100 次get()。数组长度最大 10000log2(10000)约等于 14。三次二分每轮大约 14 步每一步如果只调一次get()总量大概 42 次离 100 还很远。那为什么这道题还有不少人把调用次数跑超了第一个原因是找峰值时每轮循环需要get(mid)和get(mid1)两个位置。峰值查找就是 28 次。左段二分和右段二分各自又有 14 轮每轮也是 2 次get()各自又是 28 次。三次加起来 84 次。84 虽然低于 100但这是理想情况——你的二分模板必须非常干净不能有额外的重复访问。一旦循环边界写得不够严谨比如在循环外又补了一次get()或者某个分支收缩时多访问了一个并不需要的下标100 次很容易爆。第二个原因更隐蔽三次二分访问的下标会有大量重叠。峰值查找时已经查过的某个位置左段二分可能再查一遍右段二分可能又查一遍。如果不做缓存同样的下标被多次调用get()白白浪费调用次数。我在本地压测时的经验是用一个数组做缓存把get()的访问统一收口。比如这样写private int[] cache; private int get(MountainArray mountainArr, int index) { if (cache[index] 0) { cache[index] mountainArr.get(index) 1; } return cache[index] - 1; }这里有个小技巧山脉数组的值域是[0, 1000000]不含 -1所以缓存数组用 0 表示未访问过。为了区分真实的 0 值存入的时候加 1取出的时候减 1。这样每个下标最多只调一次真正的get()总调用次数被严格限制在被访问过的不同下标数一定小于n也自然远低于 100。如果不想用这种加一的写法也可以用boolean[] visited数组配合int[] values数组或者用MapInteger, Integer各有优劣。我个人偏好直接用int[]加一的写法因为代码最短也不容易漏初始化。加了缓存之后三次二分对get()的调用次数大概是峰值查找实际访问的不同下标约 14 个左右因为每轮的mid1在下一轮往往就变成了mid左右二分各自再新增一些下标总的不同下标数大约 40 到 50 个。非常安全。还有一个工程上的习惯值得注意同一轮循环里尽量把val先取出来不要在同一次比较里反复调用get(mid)。比如写成if (get(mid) target || get(mid) target)这种形式每轮会调用两次get()。虽然缓存能兜底但读代码的人会疑惑你到底调了几次接口调试时也容易数错调用次数。保持代码的调用语义清晰对面试讲解和后续维护都有好处。关于缓存数组的初始化我还踩过一个具体的坑。一开始我用int[]默认值 0 当作未访问但没有做加一处理。遇到目标值本身是 0 的测试用例时第一次get()返回了真实的 0缓存里存的也是 0下次再查这个下标时缓存判断0 等于未访问于是又调了一次真正的get()白白浪费次数。虽然那次没有超限但暴露了一个问题用0同时表示有效值和未访问本身就是逻辑冲突。加一技巧或者visited数组都能解决这个问题但如果你不注意它就会在某次测试里突然咬你一口。鲁棒性方面再提一点接口返回的 -1 表示没有找到这个语义要和缓存机制区分开。我自己习惯是把接口访问和业务判断彻底分层——接口访问只负责拿数值业务判断负责比较和收缩边界各司其职。这样即使后续要改缓存策略也不会影响二分逻辑的正确性。6. 一次到位的完整 Java 实现缓存与三次二分如何组合把上面的讨论拼成完整的 Java 实现。缓存数组、峰值查找、左段二分、右段二分全部组合在一起class Solution { private int[] cache; public int findInMountainArray(int target, MountainArray mountainArr) { int n mountainArr.length(); cache new int[n]; // 第一步找峰值 int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; int valMid get(mountainArr, mid); int valNext get(mountainArr, mid 1); if (valMid valNext) { l mid 1; } else { r mid; } } int peak l; // 第二步左段递增二分 int leftRes binarySearchLeft(mountainArr, target, 0, peak); if (leftRes ! -1) { return leftRes; } // 第三步右段递减二分 return binarySearchRight(mountainArr, target, peak 1, n - 1); } private int get(MountainArray mountainArr, int index) { if (cache[index] 0) { cache[index] mountainArr.get(index) 1; } return cache[index] - 1; } private int binarySearchLeft(MountainArray mountainArr, int target, int l, int r) { while (l r) { int mid l (r - l) / 2; int val get(mountainArr, mid); if (val target) return mid; if (val target) { l mid 1; } else { r mid - 1; } } return -1; } private int binarySearchRight(MountainArray mountainArr, int target, int l, int r) { while (l r) { int mid l (r - l) / 2; int val get(mountainArr, mid); if (val target) return mid; if (val target) { l mid 1; } else { r mid - 1; } } return -1; } }这段代码在 LeetCode 上可以直接通过。cache数组长度最大 10000内存开销完全可以忽略。注意右段二分的起始下标是peak 1因为peak位置在左段里已经查过。如果你不小心把右段区间写成[peak, n-1]结果也不会错但会多调一次get()去访问一个已知不可能命中的下标。一次调用确实离 100 很远但这种优化体现的是对问题的理解深度面试时主动提一句这里从 peak1 开始可以省一次访问是很加分的。找峰值时的循环条件是l r左右二分的循环条件是l r两类模板的边界规则完全不同非常容易混。我的记忆方法是找位置用l r因为位置必然存在且只有一个区间收敛到单点即可找值用l r因为值可能不存在需要让区间在收缩过程中自然退出。理解了这层区别就不会再把两个模板搞混了。7. 为什么是三次二分而不是其他方案这道题背后的本质这道题在题单里虽然标着 hard但把思路讲清楚后大部分人都能听懂。它真正考察的不是你会不会背二分模板而是你有没有理解二分查找的本质。二分查找的本质不是数组有序而是每一轮你都能根据有限的信息把答案的候选区间砍掉一半。山脉数组整体无序但它在峰值两侧各自有序所以先找峰值把问题切分成两个有序区间再在两个有序区间里各自二分——这就是标准的分治思想先把大问题拆成两个可独立求解的小问题再分别解决。我见过面试官在这道题上加问如果数组不止一个峰值怎么办比如波形起伏的山脉先升后降再升。这种问题就麻烦了。因为存在多个局部峰值时相邻两个元素的比较只能告诉你这一段是上坡还是下坡无法唯一确定你该往哪个方向收缩区间信息量不够了二分的根基就塌了。能吃透这一点才算真的理解为什么严格单峰是这道题成立的前提。和它很相似的一道题是寻找旋转排序数组中的最小值。旋转数组也有两段有序区间边界位置的查找同样是利用相邻比较加二分。两道题放在一起对比你会发现套路是完全一致的先通过一个单调性分界点把问题切成几个有序段再在段内二分。刷题时建议把这两道题放一组做比孤立地刷十道同类题效果更好。不过我也想说句实在话。这类题目的工程实战意义不在于你以后真会遇到只能通过get()访问的黑盒接口而在于它训练一种能力在数据不完全可见的情况下如何利用局部信息做全局判断。分布式系统里你拿不到全量数据只能靠局部采样做决策数据库索引的 B 树查找本质上也是一种二分决策甚至二分答案算法也是对单调性这一核心性质的反复利用。理解了这道题再看那些场景会顺畅很多。8. 我自己踩过的三个坑以及给刷题者的最终建议最后一个部分聊几个我实际踩过的坑希望能帮后来人省点调试时间。第一个坑是峰值查找里的闭区间模板。我最早写的是l r然后维护一个candidate变量在arr[mid] arr[mid1]时更新候选答案并移动右边界。这个写法也能过但代码长了三四行而且candidate的更新时机容易记错走着走着就不知道当前候选是不是最新的。后来改成l r直接收敛清爽很多也不会出现候选答案过期的问题。第二个坑是缓存数组初始值的处理。一开始我用int[]默认值 0 当未访问没有做加一处理遇到目标值是 0 的测试用例就翻车了。这个坑我在前面详细讲过这里再强调一遍凡是你要用数组缓存并且值域包含 0就必须处理0 既能表示有效值又能表示未访问的冲突。加一技巧、visited数组、Map缓存三选一但一定要选一个。第三个坑发生在右段二分。我第一次写右段时完全照抄了左段的递增模板结果目标值明明在右段却永远返回 -1。当时调试了大概二十分钟最后才反应过来是比较符号反了。递减序列的二分所有比较方向都要反过来这个反不仅仅是变还包括边界移动的方向。我的建议是右段二分的代码单独从零写一遍不要复制左段再改复制粘贴很容易遗漏某一处符号而且遗漏后特别难排查。给正在刷这道题的同学一个最终建议不要背代码一定自己动手从找峰值开始推一遍。推导的顺序是为什么相邻比较能判断方向 → 为什么峰值必然存在 → 为什么两侧各自单调 → 为什么两侧二分的比较方向相反。把这个逻辑链条捋顺了代码自然写得出来面试官怎么变形你都能应对。最后记得测试几个典型用例目标值在左段、目标值在右段、目标值恰好等于峰值、目标值在两边都不存在、目标值等于 0。这五个用例跑一遍你的实现基本就稳了。我自己在做这道题时还额外测过一个边界数组长度为 3 的最小合法山脉比如[1, 2, 1]目标值分别取 0、1、2、3。这几个小用例能帮你快速暴露峰值查找和缓存逻辑里的低级错误比直接对着大数组调试效率高得多。