双指针技巧

二分不需要有序

那个被记成前提的东西，其实不是前提

前一篇讲的都是有序数组上的二分。 几乎所有教程都会说「二分的前提是数组有序」—— 这句话不准确， 而不准确的地方恰好挡住了一大类题。

真正的前提只有一条：

每一步都能判断「答案不可能在哪一半」，从而扔掉它。

有序只是满足这条的最常见方式，不是唯一方式。 下面三类题的数组都不是全局有序的，但都能二分。

一、旋转数组：一半总是有序的

[4,5,6,7,0,1,2] 整体无序，但以 mid 切开后，必有一半是有序的—— 因为只旋转了一次，断点只有一个，它不可能同时落在两半里。

于是判据变成两步：先认出哪半有序，再看目标在不在那一半的范围内。

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {                 // 左半 [lo, mid] 有序
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                      // 那右半 [mid, hi] 必然有序
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

⭐ 只在「有序的那一半」里判断目标在不在。 无序那半没法判断， 但也不用判断 —— 目标不在有序那半，就只能在另一半。

🚨 nums[lo] <= nums[mid] 的 = 不能少。lo === mid 时（区间只剩一两个元素） 两者相等，此时左半确实“有序”（就一个元素）。写成 < 会把它误判到右半分支。

实测把 <= 换成 <：穷举长度 1–8 的全部旋转 × 每个可能的 target （含两个不存在的值），共 276 个用例，其中 6 个出错。 最小反例 [2,4,6,8,0] 找 0 —— 正确答案是下标 4，它返回 -1。 ⚠️ 注意这个反例的形状：目标就是那个最小值、且只剩最后一格。 长度 ≥ 10 的随机数组不容易撞上，所以这类错很容易被「跑了几百组随机测试」放过。

找最小值：和 nums[hi] 比，不是和 nums[lo] 比

function findMin(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] > nums[hi]) lo = mid + 1;   // ⭐ 和 nums[hi] 比
    else hi = mid;
  }
  return nums[lo];
}

⚠️ 为什么不能和 nums[lo] 比：数组可能根本没旋转过（[11,13,15,17]）。 那时 nums[mid] > nums[lo] 成立，会把你带向右边 —— 而最小值在最左边。 和 nums[hi] 比就没有这个问题：没旋转时 nums[mid] < nums[hi]，正确地往左收。

实测这个例子：和 nums[hi] 比返回 11（对），和 nums[lo] 比返回 15。 2 万个随机旋转数组里，和 nums[lo] 比错了 11520 个 —— 过半。

📌 这是个很典型的边界：「没旋转」也是一种旋转（旋转 0 位）， 而它恰好是最容易被漏掉的那个用例。

二、🚨 重复值会退化 —— 而退化程度是连续的

有重复值时（#81）， nums[lo] === nums[mid] === nums[hi] 会让人分不清哪半有序，只能两头各收一格：

if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { lo++; hi--; continue; }

流行的说法是「有重复值就会退化到 O(n)」。这句太宽 —— 但**「只有全部元素相同 才退化」也是错的**，而后者恰恰是本节以前写在这里的结论，被实测推翻了。

真正决定退化程度的量只有一个：单个值最多连续重复多少次。

⭐ 为什么是「连续」—— 这是这道题的输入约束逼出来的：#81 给的是 一个升序数组旋转而来的数组，所以相同的值必然相邻。 这一条直接决定了下面整张表。

测法：找一个不存在的值（锁住 target 那一维的最坏）， 并穷举全部 n 个旋转位取最坏（🚨 为什么必须穷举，见本节末）。 数的是 while 循环的轮数，每轮常数次比较。

不同值的种类（各占 n/k） 最长全相同段 n=1000 n=4000
1（全相同） n 500 2000 = n/2，退化到底
2 n/2 251 1001 ≈ n/4，照样退化
4 n/4 127 502 ≈ n/8
10 n/10 35 129 仍是 log n 的十倍
n/40（每个值重复 40 次） 40 21 23 开始收敛
n/8（每个值重复 8 次） 8 11 13 ≈ log n
全不同 1 10 12 = log n

⭐ 退化是连续的，不是「要么 log n 要么 n」的二选一。 粗略的形状：把区间砍到和那个全相同段一样长要 log₂(n/L) 轮， 进去以后每轮只收 2 格，于是总量由 L 主导。

🚨 所以「90% 的元素相同」必然退化（实测 n=4000 时 1610 轮）， 而不是以前写的还是 log n —— 因为数组是升序旋转来的， 「90% 相同」就等于「有一个 0.9n 长的连续段」，这两句话是同一件事。 👉 想造出「重复很多但不退化」的输入，只能让每个值都只重复几次。

⚠️ 而 [1,2,1,2,1,2,…] 这种「两种值各一半但交替」不是合法输入 —— 它不是任何升序数组的旋转（实测：6 个元素的交替数组，6 个旋转位里没有一个升序）。 📌 这是个容易踩的坑：造重复值的测试数据时，很容易造出题目根本不会给的形状， 于是量到一个安心的数字。

📌 准确的说法：最坏是 O(n)，触发它需要单个值重复 O(n) 次 —— 而在这道题的输入约束下，「重复占比高」和「单值重复次数多」不是两件事。

🚨 「找一个不存在的值」并不等于最坏路径

以前那张表错在这里，而这个坑有两层，值得单独记。

第一层：旋转位那一维没锁。 同一个数组换个旋转位，轮数差一个数量级：

最长全相同段 = 400（n=4000 的 10%，段放在数组正中，其余元素全不同）
找 -999（一个落在值域空隙里的不存在值）：
  取 32 个等距旋转位 →   12 轮   看着完全不退化
  穷举 4000 个旋转位 →  129 轮   而且只有 8 个旋转位能达到

因为退化要求「二分收敛出的那个区间整体落进全相同段」，那是个对齐条件 —— 段够长时容易撞上，段不够长时只有个别旋转位能对齐，等距抽样几乎必然漏掉。

第二层（更隐蔽）：「不存在的值」也分很多种，它们的最坏并不一样。 还是上面那个数组，穷举全部旋转位：

找 -999    （落在值域空隙里）→ 最坏 129 轮，8 个旋转位达到
找 -99999  （比所有元素都小）→ 最坏  68 轮，1 个旋转位达到

差了将近一倍。所以「找一个不存在的值」这句话根本没有锁住 target 那一维 —— 它只排除了「提前命中返回」，没排除「target 的位置让二分少绕几圈」。

⚠️ 上面那张退化表用的是「比所有元素都小」，之所以还站得住， 是因为那张表的构造里 k 种值是连续整数、各段等长，值域里没有空隙， 三种不存在的 target（比都小 / 比都大 / 值域内）实测逐格相同。 📌 这是运气好，不是通例 —— 换成段长不均的构造，第二层立刻发作。

⭐ 判据：一个「最坏情况」的实测，要问的不是「我试了多少组数据」， 而是**「最坏是几个维度的组合，我是不是每一维都取到最坏了」**。 这道题至少有三维：数据形状 × 旋转位 × 具体的 target 值。

三、峰值：数组完全无序，照样二分

这道题最能说明开头那句话。#162 给的是一个完全无序的数组（只保证相邻元素不等），要找任意一个峰 （比左右邻居都大）。看起来和二分毫无关系：

function findPeak(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;   // 上坡 → 右边必有峰
    else hi = mid;                                  // 下坡 → 左边（含 mid）必有峰
  }
  return lo;
}

⭐ 为什么成立：站在 mid 上看它和右邻居。

  • 上坡（nums[mid] < nums[mid+1]）：从 mid+1 往右走，要么一直升到边界 （边界视为负无穷，那边界就是峰），要么中途下降（下降点前一个就是峰）。 右边一定有峰。
  • 下坡：同理，左边（含 mid）一定有峰。

📌 这里被扔掉的那一半，不是「不含目标」，而是「不含所有目标中的某一个」 —— 题目只要求返回任意一个峰，所以扔掉半边完全没问题。 ⚠️ 如果题目改成「找出所有峰」，二分立刻失效。能不能二分，取决于问的是什么， 不只取决于数据长什么样。

2 万组随机数组实测（长度 1–50、相邻元素保证不等，含 499 组单元素）： 每次返回的下标都落在一个真峰上 —— 边界按题目约定视为负无穷。

四、矩阵：一个该二分，一个不该

这两道题长得几乎一样，解法却完全不同 —— 值得放在一起。

#74：每行升序， 且下一行的第一个 > 上一行的最后一个。整个矩阵摊平就是一个有序数组， 所以直接把下标 k 映射成 (k / n, k % n) 做标准二分即可。

#240：只保证 每行升序、每列升序，行与行之间没有关系。摊平不再有序，二分的前提没了。

正解是从右上角走（那个位置往左变小、往下变大，每步都能砍掉一整行或一整列）：

function searchMatrixII(matrix, target) {
  let r = 0, c = matrix[0].length - 1;      // 右上角
  while (r < matrix.length && c >= 0) {
    if (matrix[r][c] === target) return true;
    if (matrix[r][c] > target) c--;          // 当前列整列都太大 → 砍掉这一列
    else r++;                                 // 当前行整行都太小 → 砍掉这一行
  }
  return false;
}

⚠️ 很多人在 #240 上写「逐行二分」，能过，但不是最优。实测循环轮数 （矩阵取 matrix[r][c] = 2(r+c)，行列均升序）：

矩阵 target 从右上角走 逐行二分 比值
100×100 找奇数（永不命中，被迫交替走） 199 674 3.4×
400×400 同上 799 3490 4.4×
100×100 比所有元素都小 100 600 6.0×
400×400 同上 400 3200 8.0×

🚨 两组 target 差出快一倍，而这正是本节以前写错的地方。 以前只测了下面那一组（100 / 400，比值 6×→8×），却把它归因成 「O(m+n) 对 O(m·log n)」—— 可那个 target 下右上角走 只沿一个方向走了 m 步就出界了，压根没用上「每步砍掉一行或一列」的交替。 量到的其实是 O(m) 对 O(m·log n)，于是比值恰好等于 log₂n， 看着像在验证 O(m+n)，实际验证的是另一个式子。

⭐ 真最坏是让它被迫交替走（找一个永不命中、又落在值域内的 target）， 那才是 m+n−1 = 199 / 799 步。此时比值 3.4×→4.4×， 对应 m·log₂n ÷ (m+n) = log₂(m)/2 —— 差距仍随规模拉大，但只有以前写的一半。

📌 判据仍然是开头那条 —— 每一步能扔掉多少。 二分每步扔一半；右上角走每步扔一整行或一整列，在这个结构上更划算。 ⚠️ 但「扔掉一行或一列」是两种走法轮着来，估算复杂度时别只数其中一种 —— 上面那个归因错误就是这么来的。

什么时候能二分：一张判据表

数据 能二分吗 每步靠什么扔掉一半
有序数组 ✅ 比大小
旋转数组（无重复） ✅ 认出有序的那一半
旋转数组（有重复） ⚠️ 按单值最多重复几次连续退化 三点相等时分不出，只能各收一格
完全无序 + 找任意峰 ✅ 坡向指出「哪边必有峰」
完全无序 + 找所有峰 ❌ 扔掉的那半可能含答案
行列均升序的矩阵 ❌（但有 O(m+n) 解） 摊平不再有序
答案空间单调（二分答案） ✅ 可行性单调

🚨 一句话收尾：别问「这个数组有序吗」，问「我能不能判断答案不在哪一半」。 前者是后者的一个特例，而把特例当成前提，会让你在峰值和二分答案这两类题上完全想不到二分。

练习

勾选记录做过哪些，0 / 8 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。