双指针技巧

二分搜索

为什么这么容易写错

二分的思路一句话说得清，代码却是出了名的难写对。原因在于四个互相牵连的选择：

while 用 < 还是 <=
right 初值是 n - 1 还是 n
收缩时写 left = mid 还是 left = mid + 1
返回 left、right 还是 mid

这四个不能随便组合 —— 选错一个就是死循环或者差一。 背模板比现场推更靠谱，但你得知道自己在背哪一套。

模板一：找一个确切的值

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;   // 闭区间 [left, right]

  while (left <= right) {                  // 区间非空的条件
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

⭐ 记忆锚点：right = n - 1 配 <= 配 mid ± 1。三者都在说同一件事 —— 搜索区间是闭区间 [left, right]， left > right 时才算空。

🚨 如果把 <= 改成 <，left === right 那一格永远不会被检查。

⚖️ 这一篇原本写着「目标恰好落在最后一格时返回 -1，而绝大多数用例目标在中间，极容易漏过去」。两句都不对，实测（27619 次查询，目标都在数组里）：

改成 < 之后找不到的     13097 次 = 47.4%
    目标在第一格         1713 次
    目标在最后一格       2840 次
    目标在中间           8544 次   ← 「只有最后一格」不成立

原因：l === r 时循环不进入，而二分收敛到的那一格可以是任何下标，取决于数组长度和目标位置。a = [10,20,30,40,50] 上逐个找一遍：

找 10（下标 0）  ✅ 0      找 20（下标 1）  ❌ 漏
找 30（下标 2）  ✅ 2      找 40（下标 3）  ✅ 3
找 50（下标 4）  ❌ 漏

⭐ 最干净的反例是单元素数组：a = [42] 找 42，l = r = 0，循环一次都不进，直接返回 -1 —— 100% 失败。

至于「极容易漏过去」也说反了。失败率随长度变化：

长度      1     2     3     5    10    50   200
失败率 100%  54.6% 63.1% 45.4% 45.9% 37.6% 37.6%

👉 三到五成的查询会失败，随便测几个就露馅。 它难写对，但不难发现。 📌 真正「容易漏过去」的是后面那几个 —— 死循环只在长度 2 的区间触发、二分答案的下界写错要 days 够大才暴露。那些才需要专门构造用例。

模板二 / 三：找左右边界

数组里有重复元素时，「找到一个」不够用，要找第一个或最后一个。

// 左边界：第一个 >= target 的位置（不存在则返回 nums.length）
function lowerBound(nums, target) {
  let left = 0, right = nums.length;       // 🚨 开区间右端，注意不是 n-1
  while (left < right) {                   // 🚨 配 <
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;                      // 🚨 不是 mid - 1
  }
  return left;
}

// 右边界：第一个 > target 的位置
function upperBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] <= target) left = mid + 1;   // 只差这个 <=
    else right = mid;
  }
  return left;
}

⭐ 这两套模板只差一个等号。有了它们，一切都能拼出来：

target 出现次数 = upperBound - lowerBound
target 是否存在 = lowerBound < n && nums[lowerBound] === target
第一个 target 的下标 = lowerBound（存在时）
最后一个 = upperBound - 1

📌 我的建议是只背这两个，别背模板一。 lowerBound 加一句判断就等价于模板一，而边界题模板一做不了。

🚨 收缩方式与取整方向必须配对

while (left < right) 的循环要终止，每一轮都必须真的缩小区间。两个分支里至少要有一个「跨过 mid」，而且它得配上正确的取整方向。

把三种收缩方式 × 两种取整跑一遍（用「连续走同一分支」逼出最坏情况）：

写法                        向下取整      向上取整
left=mid+1 / right=mid      ✅ 收敛       💥 死循环
left=mid   / right=mid-1    💥 死循环     ✅ 收敛
left=mid   / right=mid      💥 死循环     💥 死循环

⭐ 只有两种安全组合，本文的模板用的是第一种：

left = mid + 1 / right = mid 配向下取整
left = mid / right = mid - 1 配向上取整

🚨 第三行是最常见的错法：两个分支都不跨过 mid，于是 right - left === 1 时 mid 恒等于 left（向下取整），区间一点不缩。 这种情况任何取整方向都救不了 —— 得改收缩方式，不是改取整。

⚠️ 症状是程序挂起、没有任何输出。而它只在区间缩到长度 2 时才触发。实测：

n=1  正常（区间本来就空，循环一次都不进）
n=2  挂起    n=3  挂起    n=4  挂起    n=8  挂起    n=16  挂起

🚨 注意 n=1 是唯一不触发的情况。只拿单元素数组做冒烟测试，这个死循环一次都不会现身 —— 而它一旦现身就是整个程序挂住。

📌 记法：「守」的那一边（不加减 1 的那个）决定取整方向往哪边偏 —— right 守着就向下取整，left 守着就向上取整。偏的方向要离「守方」远一点，才保证每轮都在推进。

关于 `mid` 的写法

left + Math.floor((right - left) / 2) 比 Math.floor((left + right) / 2) 更好，是为了防止 left + right 溢出 —— 但 JavaScript 里这个溢出基本不会发生，而且 JS 的症状和 Java/C++ 那个经典 bug 不是一回事：定长整型会绕成负数，而 JS 的 Number 是浮点，超过 2⁵³ 只是丢精度。数组下标又到不了那个量级。

📌 四组边界值的实测对照、以及「那还写不写」的结论，在双指针技巧里（mid 属于那一篇的「左右指针」那一节，不在这里重复一遍）。一句话版本：写，但理由是换语言时不会栽 —— 同一行在 Java 里是真 bug，JDK 的 Arrays.binarySearch 里潜伏了九年。

⭐ 二分答案：这一节才是二分真正的价值

前面都是「在有序数组里查找」。但面试里更常见的是这样一类题：

求满足某个条件的最小/最大值。

它们表面上跟二分没关系，但只要答案的可行性是单调的，就能二分：

如果 x 可行，那么所有比 x 大的也可行（或者反过来）

有了这条单调性，「求最小可行值」就变成了「在 [lo, hi] 上找第一个可行的位置」—— 正是 lowerBound。

例：运送包裹的最小载重

题意复述：一批货物要在 days 天内按顺序运完，每天不能超过船的载重量，问船的最小载重是多少。

function shipWithinDays(weights, days) {
  // 判定：载重 cap 能否在 days 天内运完
  const feasible = (cap) => {
    let need = 1, cur = 0;
    for (const w of weights) {
      if (cur + w > cap) { need++; cur = 0; }
      cur += w;
    }
    return need <= days;
  };

  // 🚨 下界是「最重的那件货」——比它小的载重连一件都装不下
  let left = Math.max(...weights);
  // 上界是「全部货物总重」——一天运完，一定可行
  let right = weights.reduce((a, b) => a + b, 0);

  while (left < right) {                    // 就是 lowerBound
    const mid = left + Math.floor((right - left) / 2);
    if (feasible(mid)) right = mid;         // 可行 → 试试更小的
    else left = mid + 1;
  }
  return left;
}

⭐ 这类题的难点从来不是二分，是那三件事：

答案的范围 —— 上下界取错会漏掉正确答案，或者白跑很多轮
feasible 怎么写 —— 通常是一个 O(n) 的贪心模拟
单调性成立吗 —— 载重越大越容易运完，成立；不成立就不能二分

🚨 第 1 条最容易错，而且错法很会藏。下界写成 1 会怎样？

上面那个 feasible 并不检查「单件货是否装得下」—— 遇到超重的货它只是新开一天，让 cur 超过 cap。所以当 days 足够大时，它会对荒谬的载重返回 true：

w=[3,2,2,4,1,4], days=3   下界=max → 6   下界=1 → 6    （碰巧相同）
w=[3,2,2,4,1,4], days=6   下界=max → 4   下界=1 → 3    ❌
w=[5],           days=2   下界=max → 5   下界=1 → 1    ❌

⚠️ 上面那三行是实测输出（逐格复现过）。规律没有「只有 days >= 件数才暴露」那么干净 —— 4000 组随机用例分两边统计：

days >= 货物件数    2845 组中 2699 组暴露 = 94.9%
days <  货物件数    1155 组中  171 组暴露 = 14.8%

⭐ days >= 件数时几乎必然暴露（那时「每件货单独一天」总够用， feasible(1) 直接误判成可行）；但 days < 件数 时仍有一成半会暴露，不是「测不出来」。

📌 所以别指望「我的用例 days 都很小所以没事」—— 七分之一的概率撞上，而撞上时答案偏小，看起来只是「算得不太对」。

⭐ 两种修法，选一个：把下界设成 max(weights)（本文的做法），或者在 feasible 里显式判 if (w > cap) return false。别两个都不做。

📌 判据：题目问「最小的最大值」「最大的最小值」「至少需要多少」—— 这类措辞几乎就是在提示二分答案。

往后看：不有序也能二分

上面所有例子的前提都是「数组有序」。但那不是二分真正的前提 —— 真正的前提是「每一步能判断答案不在哪一半」，有序只是满足它最常见的方式。

旋转数组、完全无序的峰值问题、二维矩阵，都能二分（或不能，而理由很值得想清楚）：见二分不需要有序。

复杂度

查找是 O(log n)。二分答案是 O(n log M)，其中 M 是答案的取值范围 —— 每轮二分要跑一次 O(n) 的 feasible。

⚠️ 注意 log 里是值域不是数组长度。数一下 feasible 被调用了多少次就清楚了：

数组长度 n	值域 M	`feasible` 调用次数	log₂M	log₂n
100	598	9	9.2	6.6
100	43,759,151	26	25.4	6.6
10,000	54,807	16	15.7	13.3
10,000	4,962,468,676	32	32.2	13.3

⭐ 调用次数逐行贴着 log₂M，和 log₂n 完全无关 —— 第 1 行和第 2 行 n 一样都是 100，只因值域差 7 万倍，调用次数就从 9 涨到 26。

📌 值域很大（比如 10⁹）时 log 约等于 30，仍然很快；但如果 feasible 本身是 O(n²)，整体就吃不消了。

练习

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

704. 二分查找简单裸的二分
35. 搜索插入位置简单就是 lowerBound
34. 在排序数组中查找元素的第一个和最后一个位置中等左右边界两套模板一起用
875. 爱吃香蕉的珂珂中等⭐ 二分答案的入门题，注意下界
1011. 在 D 天内送达包裹的能力中等二分答案；下界必须是 max(weights)
410. 分割数组的最大值困难二分答案的难题，「最小的最大值」

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