二分查找

// 第一个 >= target 的位置
function lowerBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

// 第一个 > target 的位置
function upperBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
}

模板不死循环的关键是两点：mid 向下取整，所以 mid < right 恒成立，right = mid 至少收缩一格；left = mid + 1 也严格前进。反过来，闭区间里写 right = mid，当 left === right 时 mid === left，区间不再变化，就会卡死。

二分不止用于有序数组

二分的本质是在单调函数上找分界点：存在一个谓词 check(i)，前半段全为 false、后半段全为 true，二分就是找第一个 true。数组有序只是"nums[i] >= target 单调"的一个特例；旋转数组、山峰数组、答案空间只要满足单调，同样可以二分。

旋转数组的最小值、峰值元素靠"局部趋势"构造谓词；二分答案则把"求最小的可行值"转成"判定某个值是否可行"，判定函数往往是一次 O(n) 扫描。

常见误区

很多人以为二分必须全局有序，实际上只需要所查找的判定条件单调，旋转数组和峰值题都不满足全局有序。

很多人以为 JS 没有整数溢出所以 (left + right) / 2 绝对安全，实际上 >> 1 会把结果截断成 32 位有符号数。

很多人以为 while (left <= right) 可以配 right = mid，实际上这两者混用会在区间只剩一个元素时死循环。

常考题型

搜索插入位置

等价于 lower_bound：找到第一个大于等于 target 的位置，找不到时返回数组长度。时间 O(log n)，空间 O(1)。

function searchInsert(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

搜索旋转排序数组

每次二分必有一半是有序的，判断 target 是否落在有序那一半的值域内，决定保留哪一半。时间 O(log n)，空间 O(1)。

function searchRotated(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

寻找峰值

若 nums[mid] < nums[mid + 1]，右侧一定存在峰值，把 left 移到 mid+1；否则峰值在左侧或 mid 本身。时间 O(log n)，空间 O(1)。

function findPeakElement(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] < nums[mid + 1]) left = mid + 1;
    else right = mid;
  }
  return left;
}

爱吃香蕉的珂珂

速度 k 越大，吃完所有香蕉的时间越少，时间是 k 的单调递减函数。在 [1, max(piles)] 上二分最小的可行速度，判定函数累加 ceil(pile / k)。时间 O(n log m)，空间 O(1)。

function minEatingSpeed(piles, h) {
  let left = 1, right = Math.max(...piles);
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / mid);
    if (hours <= h) right = mid;
    else left = mid + 1;
  }
  return left;
}

关联阅读

• 排序算法：有序是二分的前提，排序题常紧接着二分
• 双指针与滑动窗口：同样是利用单调性把 O(n²) 压成 O(n)
• 本目录说明：高级算法的整体学习路径