算法篇 ｜ 二分法

前言

二分查找（Binary Search）可能是你最早接触的算法之一——在一个有序数组中查找目标值，每次把搜索范围缩小一半，时间复杂度 O(log n)。看起来很简单对吧？

但实际上，二分法是最容易写错的算法之一。循环条件是 < 还是 <=？右边界是 mid 还是 mid - 1？返回 left 还是 right？稍有不慎就是死循环或者越界。

正如 Donald Knuth 所说：“虽然基本思想很简单，但细节可以令人抓狂。”

更关键的是，面试中的二分法题目很少考最基础的”查找一个数”，更多考的是变体——查找左边界、右边界、旋转数组、山脉数组等等。如果你只背了一个基础模板，碰到变体就会手忙脚乱。

本章我们会从最基础的二分开始，然后重点讲解左边界二分、右边界二分，给出一个统一的模板写法，最后通过经典 LeetCode 题目帮你把这个模板彻底练熟。

诊断自测

Q1：在有序数组 [1, 2, 3, 3, 3, 4, 5] 中，如何找到第一个 3 的位置？如何找到最后一个 3 的位置？

Q2：二分查找的循环条件 left < right 和 left <= right 有什么区别？什么时候用哪个？

一、基础二分查找

先从最简单的开始：在一个有序数组中查找一个目标值，存在就返回下标，不存在返回 -1。

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

几个细节：

1. mid = left + Math.floor((right - left) / 2) 而不是 (left + right) / 2，是为了防止 left + right 整数溢出。虽然在 JavaScript 中数字是浮点数，不太会溢出，但这是一个好习惯。

2. 循环条件 left <= right 意味着搜索区间是闭区间 [left, right]。当 left > right 时，区间为空，搜索结束。

3. left = mid + 1 和 right = mid - 1 是因为 nums[mid] 已经检查过了，不需要再包含在搜索区间中。

复杂度分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

二、左边界二分

基础二分找到目标就返回了，但如果数组中有多个相同的目标值，它返回的是哪一个？不确定。

左边界二分的目标是：找到目标值的第一个位置（或者说，找到第一个 >= target 的位置）。

function leftBound(nums, target) {
  let left = 0;
  let right = nums.length; // 注意：右边界是 nums.length，不是 nums.length - 1

  while (left < right) {  // 注意：是 < 不是 <=
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid; // 注意：是 mid 不是 mid - 1
    }
  }

  return left; // left 就是第一个 >= target 的位置
}

和基础二分的区别：

1. 搜索区间是 [left, right)（左闭右开），所以 right 初始值是 nums.length，循环条件是 left < right
2. 找到 target 时不立即返回，而是缩小右边界继续向左搜索
3. right = mid 而不是 mid - 1，因为搜索区间是左闭右开，mid 不会被包含在下一轮的搜索范围中

如何判断目标是否存在？

function searchLeftBound(nums, target) {
  const idx = leftBound(nums, target);
  if (idx >= nums.length || nums[idx] !== target) {
    return -1;
  }
  return idx;
}

三、右边界二分

右边界二分的目标是：找到目标值的最后一个位置。

function rightBound(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] <= target) {
      left = mid + 1; // 注意：找到 target 时收缩左边界
    } else {
      right = mid;
    }
  }

  return left - 1; // left - 1 就是最后一个 <= target 的位置
}

关键区别：找到 target 时，不是收缩右边界，而是收缩左边界（left = mid + 1），继续向右搜索。最终 left - 1 就是最后一个 target 的位置。

四、统一模板

你可能已经发现了，左边界和右边界二分的结构非常相似，唯一的区别在于 “找到目标时怎么做”：

• 左边界：nums[mid] >= target 时收缩右边界 → 向左逼近
• 右边界：nums[mid] <= target 时收缩左边界 → 向右逼近

我们可以把它们统一成一个模板，通过一个条件函数来控制行为：

// 统一的二分模板：找到第一个满足条件的位置
function binarySearchFirst(nums, condition) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (condition(nums[mid])) {
      right = mid;  // 满足条件，收缩右边界
    } else {
      left = mid + 1; // 不满足，收缩左边界
    }
  }

  return left;
}

// 左边界：第一个 >= target 的位置
const leftIdx = binarySearchFirst(nums, (x) => x >= target);

// 右边界：第一个 > target 的位置 - 1
const rightIdx = binarySearchFirst(nums, (x) => x > target) - 1;

这个模板的核心思想：二分法本质上是在一个”单调的布尔序列”上找到分界点。对于 [F, F, F, T, T, T] 这样的序列，我们要找第一个 T 的位置。不管原问题是什么，都可以转化成这个形式。

五、经典题目

5.1 在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

给定一个升序数组 nums 和一个目标值 target，找出 target 在数组中的起始位置和结束位置。如果不存在，返回 [-1, -1]。

function searchRange(nums, target) {
  const left = leftBound(nums, target);
  const right = rightBound(nums, target);

  // 检查 target 是否存在
  if (left > right) {
    return [-1, -1];
  }
  return [left, right];
}

function leftBound(nums, target) {
  let lo = 0;
  let hi = nums.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

function rightBound(nums, target) {
  let lo = 0;
  let hi = nums.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] <= target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo - 1;
}

复杂度分析：

• 时间复杂度：O(log n)，两次二分
• 空间复杂度：O(1)

5.2 搜索旋转排序数组（LeetCode 33）

一个升序数组在某个位置被旋转了（如 [4,5,6,7,0,1,2]），在其中搜索目标值 target，存在返回下标，不存在返回 -1。

这道题的难点在于数组不是完全有序的。但有一个关键性质：旋转后的数组，至少有一半是有序的。

function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    // 判断哪半边是有序的
    if (nums[left] <= nums[mid]) {
      // 左半边有序
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1; // target 在左半边
      } else {
        left = mid + 1;  // target 在右半边
      }
    } else {
      // 右半边有序
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;  // target 在右半边
      } else {
        right = mid - 1; // target 在左半边
      }
    }
  }

  return -1;
}

思路解析：

1. 计算 mid 后，先判断左半部分 [left, mid] 和右半部分 [mid, right] 哪个是有序的
2. 如果 nums[left] <= nums[mid]，左半部分有序。检查 target 是否在左半部分的范围内
3. 否则右半部分有序，检查 target 是否在右半部分的范围内
4. 确定 target 所在的那半边后，缩小搜索范围

复杂度分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

5.3 寻找旋转排序数组中的最小值（LeetCode 153）

一个升序数组在某个位置被旋转了，找出数组中的最小值。

function findMin(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] > nums[right]) {
      // mid 在旋转点左边，最小值在右半边
      left = mid + 1;
    } else {
      // mid 在旋转点右边或没有旋转，最小值在左半边（包括 mid）
      right = mid;
    }
  }

  return nums[left];
}

复杂度分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

六、二分法的本质

很多人觉得二分法只能用在”有序数组”上，但其实不是。二分法的本质是：

在一个具有某种”二段性”的序列上，利用判断条件把搜索范围缩小一半。

“二段性”是指：存在一个分界点，分界点左边的元素都满足某个条件，右边都不满足（或反过来）。有序数组只是最简单的一种二段性。

举几个例子：

• 旋转排序数组：分界点左边 >= nums[0]，右边 < nums[0]
• 山脉数组：分界点左边递增，右边递减
• 求平方根：分界点左边 x² <= n，右边 x² > n

所以当你遇到一道题，如果能找到一种”二段性”（或者说，一个单调的布尔函数），就可以考虑用二分法。

常见误区

误区一：“二分法只能用在有序数组上”

如上所述，二分法的适用条件是”二段性”，不一定需要全局有序。旋转排序数组、山脉数组、甚至某些”最大化最小值”的问题（二分答案），都可以用二分法。

误区二：“循环条件统一用 left <= right 就行了”

left <= right 对应闭区间写法，left < right 对应左闭右开写法。两种都可以，但必须和右边界的更新方式匹配。闭区间写法中 right = mid - 1，左闭右开写法中 right = mid。混用就会出 Bug（死循环或跳过元素）。

误区三：“mid 用 (left + right) / 2 就行了”

在 JavaScript 中这样写不太会出问题（数字是浮点数），但 left + right 在其他语言中可能整数溢出。正确写法是 left + Math.floor((right - left) / 2)。养成好习惯，面试时也不会被挑刺。

误区四：“二分查找一定比线性查找快”

只有在数据量足够大、且数据具有二段性时，O(log n) 才显著优于 O(n)。对于小数组（比如长度 < 10），二分查找的常数因子和复杂的边界判断反而可能使它比线性查找更慢。此外，如果数据没有二段性，二分法根本不适用。

小结

二分法看似简单，但要写对并不容易。本章我们从基础二分出发，重点讲解了左边界和右边界的变体，并给出了统一的模板。

核心要点

1. 基础二分：闭区间 [left, right]，找到就返回，left <= right
2. 左边界二分：找第一个 >= target 的位置，找到 target 时收缩右边界
3. 右边界二分：找最后一个 <= target 的位置，找到 target 时收缩左边界
4. 统一模板：二分本质是在单调布尔序列上找分界点
5. 二段性：二分法的适用条件不是”有序”，而是”二段性”
6. 注意事项：循环条件和边界更新必须匹配，mid 的计算要防溢出

本章思维导图

练习挑战

第一题 ⭐：x 的平方根（LeetCode 69）

给定一个非负整数 x，计算并返回 x 的算术平方根（向下取整）。

// 示例
// 输入: x = 8
// 输出: 2（因为 √8 = 2.828...，向下取整为 2）

function mySqrt(x) {
  let left = 0;
  let right = x;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (mid * mid === x) {
      return mid;
    } else if (mid * mid < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return right; // right 就是 ≤ √x 的最大整数
}

第二题 ⭐⭐：搜索二维矩阵（LeetCode 74）

给定一个 m x n 矩阵 matrix，每行从左到右升序，每行的第一个数大于上一行的最后一个数。判断目标值 target 是否在矩阵中。

function searchMatrix(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    // 将一维索引转换为二维坐标
    const row = Math.floor(mid / n);
    const col = mid % n;
    const val = matrix[row][col];

    if (val === target) {
      return true;
    } else if (val < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

第三题 ⭐⭐⭐：寻找两个正序数组的中位数（LeetCode 4）

给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，找出这两个正序数组的中位数。要求时间复杂度 O(log(m+n))。

function findMedianSortedArrays(nums1, nums2) {
  // 确保 nums1 是较短的数组
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  const m = nums1.length;
  const n = nums2.length;
  let left = 0;
  let right = m;

  while (left <= right) {
    // i 是 nums1 的分割点，j 是 nums2 的分割点
    const i = left + Math.floor((right - left) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;

    const nums1Left = i === 0 ? -Infinity : nums1[i - 1];
    const nums1Right = i === m ? Infinity : nums1[i];
    const nums2Left = j === 0 ? -Infinity : nums2[j - 1];
    const nums2Right = j === n ? Infinity : nums2[j];

    if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
      // 找到正确的分割点
      if ((m + n) % 2 === 1) {
        return Math.max(nums1Left, nums2Left);
      } else {
        return (
          (Math.max(nums1Left, nums2Left) +
            Math.min(nums1Right, nums2Right)) /
          2
        );
      }
    } else if (nums1Left > nums2Right) {
      right = i - 1;
    } else {
      left = i + 1;
    }
  }

  return 0;
}

自我检测

• 能默写基础二分查找，并解释循环条件和边界更新的逻辑
• 能说清楚 left <= right（闭区间）和 left < right（左闭右开）两种写法的区别
• 能写出左边界二分和右边界二分，并解释各自在”找到 target 时”的不同行为
• 能用统一模板把二分问题转化为”在单调布尔序列上找分界点”
• 能解决旋转排序数组的查找问题，并解释”哪半边有序”的判断逻辑
• 能解释二分法的本质——“二段性”，而不仅仅是”有序性”
• 能解释为什么 mid = left + Math.floor((right - left) / 2) 比 (left + right) / 2 更安全
• 能在面试中快速选择合适的二分模板并正确实现