一个先单调递增再单调递减的数组，给一个目标值，判断目标值是否在数组中？｜阿里巴巴算法面经解析

60 秒回答模板

可以按三步展开：第一，说明数组是一个双调数组，整体不是单调的，但峰值两侧分别单调；第二，用二分比较 mid 和 mid+1 的大小来判断峰值在左边还是右边，从而找到峰值下标；第三，先判断目标值是否等于峰值，若不是，再在 [0, peak-1] 上按升序二分，在 [peak+1, n-1] 上按降序二分。边界上，空数组直接返回 false，长度为 1 或 2 时可以直接处理或让统一逻辑覆盖；全增数组的峰值在末尾，全减数组的峰值在开头，也能被峰值二分自然覆盖。若题目允许非严格单调或峰值重复，需要额外定义重复平台如何处理，否则普通严格双调写法可能漏判或退化。

考点 问题建模

主线 峰值查找

易错点 把整个数组当成升序数组做一次普通二分，导致在下降段时错…

深入解析

问题建模

数组先单调递增再单调递减，说明它不是全局有序数组，而是由两个有序区间拼接而成：左半部分升序，右半部分降序，中间存在一个最大值位置，也就是峰值。普通二分要求整个搜索区间有统一的单调方向，这里全数组不满足，所以不能把目标值直接和中点比较后就丢掉一半。正确建模是先恢复出两个可二分的单调区间，再分别查找。

峰值查找

峰值可以用二分在 O(log n) 内找到。核心判断是比较 nums[mid] 和 nums[mid+1]：如果 nums[mid] 小于 nums[mid+1]，说明当前位置还在上升坡上，峰值一定在 mid 右侧；否则说明已经到达下降坡或峰值左边界附近，峰值在 mid 或 mid 左侧。不断收缩区间，最终 low 和 high 相遇的位置就是一个峰值位置。这个过程不依赖目标值，只利用数组的双调结构。

分段二分

找到峰值以后，目标值的查找分三种情况。第一，如果 target 等于 nums[peak]，立即返回 true。第二，在峰值左侧的递增段执行升序二分：target 小于中点值时往左找，大于中点值时往右找。第三，在峰值右侧的递减段执行降序二分：target 小于中点值时往右找，大于中点值时往左找。左右两段任意一段找到即可返回 true，否则返回 false。

复杂度分析

峰值查找是一次二分，复杂度 O(log n)；左侧二分最多 O(log n)，右侧二分最多 O(log n)。三者相加仍然是 O(log n)。整个过程中只使用常数个指针变量，因此空间复杂度是 O(1)。这也是该题的关键优化点：利用结构把线性扫描降到对数级。

为什么不能线性扫

线性扫描当然能判断目标值是否存在，但复杂度是 O(n)，没有利用数组先升后降的已知条件。题目特意给出单调递增再递减，就是希望识别双调数组，并设计二分方案。如果只从头到尾扫描，虽然正确性没问题，但算法层级偏低，无法体现对有序结构的利用。

全增全减边界

如果数组实际是全递增，可以把峰值视为最后一个元素，左侧是完整升序区间，右侧为空；如果数组实际是全递减，可以把峰值视为第一个元素，左侧为空，右侧是完整降序区间。用比较 nums[mid] 和 nums[mid+1] 的峰值二分仍能自然处理这两类情况，只要循环边界保证 mid+1 不越界。

严格与非严格单调

若题目默认严格单调递增再严格单调递减，峰值唯一，二分逻辑最简单。若允许非严格单调，例如存在相邻相等元素，峰值可能是一段平台，比较 nums[mid] 和 nums[mid+1] 相等时无法明确判断峰值方向。此时需要重新定义策略：可以先找到平台边界，再在两侧查找；也可以在相等时收缩边界，但最坏情况下可能退化到 O(n)。

javascript

先找峰值，再二分两侧

function containsBitonic(nums, target) {
  const peak = findPeak(nums);
  return binarySearch(nums, target, 0, peak, true) ||
    binarySearch(nums, target, peak + 1, nums.length - 1, false);
}

function findPeak(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[mid + 1]) left = mid + 1;
    else right = mid;
  }
  return left;
}

单峰数组不能直接整体二分，先定位峰值，再分别按升序和降序二分。
面试时要补充空数组、全升序/全降序、重复元素这几个边界是否允许。

易错点

把整个数组当成升序数组做一次普通二分，导致在下降段时错误丢弃搜索区间。
找到峰值后只搜索一侧，忘记目标值可能位于另一侧。
右侧递减区间仍然按升序二分写，比较方向反了。
没有先处理空数组，导致访问 nums[0] 或 nums[mid+1] 越界。
峰值查找循环中 mid+1 越界，通常是 high 和循环条件设置不严谨。
默认峰值唯一，但题目若允许相等元素时没有说明重复平台的处理方式。

面试官追问

如果数组是全递增，还能用这个方法吗？

可以。全递增可以看作峰值在最后一个位置，右侧递减区间为空。找到峰值后，只需要在左侧升序区间查找，复杂度仍是 O(log n)。

如果数组是全递减，还能用这个方法吗？

可以。全递减可以看作峰值在第一个位置，左侧递增区间为空。峰值不等于目标时，只需要在右侧降序区间二分即可，整体仍然保持 O(log n) 时间复杂度。

如果 target 大于峰值，可以怎么优化？

峰值是数组最大值。如果 target 大于 nums[peak]，可以直接返回 false，不需要再搜索两侧区间。

如果存在多个相同峰值怎么办？

这属于非严格双调。需要先明确题目是否允许相等。如果允许，可以把峰值平台看作一段最大值区间，先判断 target 是否等于平台值，再在平台左侧升序段和平台右侧降序段查找。但在大量重复元素存在时，部分二分判断可能失去方向性，最坏复杂度可能退化。

为什么不能边找峰值边找 target？

可以做一些剪枝，例如中点等于 target 时立即返回 true，但一般不建议把逻辑写得过度耦合。先找峰值再分段二分，正确性更清晰，边界更容易证明。