二分查找

讲解

二分查找的思想朴素至极：在有序序列里，每次看中间元素，就能把一半的候选排除掉，O(log n) 次比较定位目标——n 为一百万时只要约 20 次比较。但它的正确性细节是出了名的多：循环条件写 left <= right 还是 left < right？mid 之后 right 取 mid - 1 还是 mid？写错一处就是死循环或漏解。对策是固定一套「区间语义」并始终坚持：本章用「闭区间 [lo, hi]」配 left <= right、两侧都越过 mid 写标准查找；用「左闭右开 [lo, hi)」配 left < right、right = mid 写边界查找。

比记模板更重要的是理解「边界变体」在做什么。lower_bound 找第一个 >= target 的位置：当 nums[mid] >= target 时，mid 可能是答案，但左边可能还有，于是 hi = mid 继续向左压；最终 lo 停在插入点上。upper_bound 找第一个 > target 的位置，只差一个比较符号。两者一减就是 target 的出现次数——有序数组里的统计问题全被这两个变体覆盖。

二分最大的进阶是「二分答案」：当答案本身单调（速度越快耗时越少、运力越大天数越少），而验证一个答案是否可行是 O(n) 时，就可以对答案空间二分。「爱吃香蕉的珂珂」是标准像：吃的速度 v 单调，验证 f(v) = 总耗时 <= h 是线性扫描，于是对 v 二分找最小可行值。识别信号：题目问「最小的最大值」或「最大的最小值」且可行性能快速验证。

旋转排序数组的查找则展示二分的另一面：数组不完全有序，但任意一刀切开，必有一半是有序的——先判断哪半有序，再看目标在不在那半的范围内，每次仍能排除一半。

示例

标准二分、lower/upper bound、旋转数组查找、二分答案（珂珂吃香蕉）一次给全：

import assert from 'node:assert/strict';

// 闭区间标准二分：找到返回下标，找不到返回 -1
function binarySearch(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// 左闭右开：第一个 >= target 的下标（不存在则为 nums.length）
function lowerBound(nums, target) {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// 第一个 > target 的下标
function upperBound(nums, target) {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// 旋转排序数组：总有一半有序，判目标是否落在有序半内
function searchRotated(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      // 左半有序
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // 右半有序
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

// 二分答案：最小速度 v 使总耗时 <= h
function minEatingSpeed(piles, h) {
  function hoursNeeded(speed) {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / speed);
    return hours;
  }
  let lo = 1;
  let hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (hoursNeeded(mid) <= h) hi = mid; // mid 可行，往更慢压
    else lo = mid + 1; // mid 不可行，必须更快
  }
  return lo;
}

assert.strictEqual(binarySearch([1, 3, 5, 7, 9], 7), 3);
assert.strictEqual(binarySearch([1, 3, 5, 7, 9], 4), -1);
assert.strictEqual(lowerBound([1, 2, 2, 2, 3], 2), 1);
assert.strictEqual(upperBound([1, 2, 2, 2, 3], 2), 4); // 出现次数 = 4 - 1 = 3
assert.strictEqual(lowerBound([1, 3, 5], 4), 2); // 插入点
assert.strictEqual(searchRotated([4, 5, 6, 7, 0, 1, 2], 0), 4);
assert.strictEqual(searchRotated([4, 5, 6, 7, 0, 1, 2], 3), -1);
assert.strictEqual(minEatingSpeed([3, 6, 7, 11], 8), 4);
assert.strictEqual(minEatingSpeed([30, 11, 23, 4, 20], 5), 30);

console.log('二分查找示例全部通过');

用 lower/upper bound 的组合再体会一次威力：有序数组中 target 的出现次数 = upperBound - lowerBound，查找插入位置 = lowerBound——两个原语覆盖一整族题目。

常见坑

• 区间语义混用：闭区间配 left <= right、hi = mid - 1；左闭右开配 left < right、hi = mid。两套混着写必然死循环或漏边界。
• 中点溢出的旧问题：别的语言里 (lo + hi) / 2 可能整数溢出，要写 lo + ((hi - lo) >> 1)；JS 数字是双精度浮点，安全范围内不溢出，但位运算 >> 会按 32 位截断——超出 2³¹ 的下标不要用 >>。
• 死循环自查：循环体里必须保证 lo 或 hi 至少一个变化且向彼此逼近；写完后脑测 lo + 1 === hi 的两元素情形。
• 以为二分只能用在数组：答案单调即可二分（珂珂、运货、分割数组最大值），数据本身无需有序。
• 旋转数组判断错有序半：nums[lo] <= nums[mid] 判左半有序（等号必须带，两元素时 lo === mid）；落在哪半再比较目标与端点。

小结

二分 = 每次排除一半候选，O(log n)；固定一套区间语义贯彻到底；lower/upper bound 两原语覆盖边界统计；答案单调即可二分答案。下一章把「有序」本身造出来：排序算法。