跳到主要内容

二分查找

什么是二分查找？​

二分查找是一种在有序数组中查找目标值的算法。每次比较中间元素，将搜索范围缩小一半。

时间复杂度：O(log n)
空间复杂度：O(1)
前提条件：数组必须有序
为什么叫「二分」？

因为每次都把搜索范围一分为二，只保留可能包含目标的那一半。

基础模板​

标准二分查找​

binary-search.ts
function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

    if (nums[mid] === target) {
      return mid;  // 找到目标，返回索引
    } else if (nums[mid] < target) {
      left = mid + 1;  // 目标在右半部分
    } else {
      right = mid - 1;  // 目标在左半部分
    }
  }

  return -1;  // 没找到
}

执行过程示例​

nums = [1, 3, 5, 7, 9, 11], target = 7

第 1 次：left=0, right=5, mid=2
         nums[2]=5 < 7，向右找
         left = 3

第 2 次：left=3, right=5, mid=4
         nums[4]=9 > 7，向左找
         right = 3

第 3 次：left=3, right=3, mid=3
         nums[3]=7 === 7，找到！
         返回 3

边界条件详解​

二分查找最容易出错的地方就是边界条件。

为什么是 left <= right？​

// ✅ 正确：left <= right
while (left <= right)

// ❌ 错误：left < right
while (left < right)  // 会漏掉 left === right 的情况

例子：nums = [1], target = 1

  • 如果用 left < right：循环根本不会执行，返回 -1（错误）
  • 如果用 left <= right：会检查 nums[0]，返回 0（正确）

为什么是 left = mid + 1？​

// ✅ 正确
if (nums[mid] < target) {
  left = mid + 1;
}

// ❌ 错误
if (nums[mid] < target) {
  left = mid;  // 可能导致死循环
}

因为 nums[mid] 已经比较过了，不需要再包含在搜索范围内。

常见变体​

变体 1：查找第一个等于目标的位置​

当数组中有重复元素时，找到最左边那个。

function findFirst(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

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

    if (nums[mid] === target) {
      result = mid;      // 记录答案
      right = mid - 1;   // 继续向左找
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

// 示例
// nums = [1, 2, 2, 2, 3], target = 2
// 返回 1（第一个 2 的位置）

变体 2：查找最后一个等于目标的位置​

function findLast(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

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

    if (nums[mid] === target) {
      result = mid;      // 记录答案
      left = mid + 1;    // 继续向右找
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

// 示例
// nums = [1, 2, 2, 2, 3], target = 2
// 返回 3（最后一个 2 的位置）

变体 3：查找插入位置​

找到目标应该插入的位置（保持数组有序）。

function searchInsert(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

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

  return left;  // 返回 left 就是插入位置
}

// 示例
// nums = [1, 3, 5, 7], target = 4
// 返回 2（4 应该插入到位置 2）

变体 4：查找第一个大于等于目标的位置​

也叫 lower_bound。

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;  // 注意：right 是 length，不是 length - 1

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

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

  return left;
}

// 示例
// nums = [1, 3, 5, 7, 9], target = 4
// 返回 2（nums[2]=5 是第一个 >= 4 的）

二分查找的两种写法​

写法一：左闭右闭 [left, right]​

function binarySearch1(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;  // 右边界是最后一个元素

  while (left <= right) {       // 因为 right 是有效索引，所以可以取等
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;       // right 也要 -1
  }

  return -1;
}

写法二：左闭右开 [left, right)​

function binarySearch2(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;      // 右边界是数组长度（取不到）

  while (left < right) {        // 因为 right 取不到，所以不能取等
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid;           // right 直接赋值，不用 -1
  }

  return -1;
}
推荐

建议熟练掌握写法一（左闭右闭），逻辑更直观，不容易出错。

应用场景​

1. 有序数组查找​

最基本的应用，直接套用模板。

2. 旋转有序数组​

// [4, 5, 6, 7, 0, 1, 2] 中查找 target
function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

    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;
}

3. 求平方根​

function mySqrt(x: number): number {
  if (x < 2) return x;

  let left = 1;
  let right = Math.floor(x / 2);

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

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

  return right;  // 返回最大的 mid 使得 mid² <= x
}

4. 查找峰值​

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;

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

    if (nums[mid] > nums[mid + 1]) {
      // 峰值在左边（包括 mid）
      right = mid;
    } else {
      // 峰值在右边
      left = mid + 1;
    }
  }

  return left;
}

常见错误​

错误 1：整数溢出​

// ❌ 可能溢出（在其他语言中）
const mid = (left + right) / 2;

// ✅ 安全写法
const mid = left + Math.floor((right - left) / 2);

// 在 JavaScript 中通常不会溢出，但养成好习惯

错误 2：死循环​

// ❌ 可能死循环
while (left < right) {
  const mid = Math.floor((left + right) / 2);
  if (nums[mid] < target) {
    left = mid;  // 错！当 left + 1 === right 时会死循环
  }
}

// ✅ 正确
left = mid + 1;

错误 3：边界处理​

// ❌ 没考虑空数组
function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;  // 空数组时 right = -1
  // ...
}

// ✅ 先判断
function search(nums: number[], target: number): number {
  if (nums.length === 0) return -1;
  // ...
}

二分查找 Checklist​

□ 数组是有序的吗？
□ 用的是 left <= right 还是 left < right？
□ right 初始值是 length 还是 length - 1？
□ 更新 left/right 时有没有 +1/-1？
□ 返回值是 left、right 还是 mid？
□ 空数组、单元素数组测试过了吗？

LeetCode 练习题​

难度题目链接
简单704. 二分查找LeetCode
简单35. 搜索插入位置LeetCode
简单69. x 的平方根LeetCode
中等34. 排序数组中查找元素LeetCode
中等33. 搜索旋转排序数组LeetCode
中等162. 寻找峰值LeetCode

常见面试问题​

Q1: 二分查找的前提条件是什么？​

答案：

严格来说，二分查找要求数据满足单调性（不一定是有序数组）：

  1. 有序数组：最典型的场景
  2. 旋转有序数组：局部有序，也可以二分
  3. 山脉数组/峰值问题：先增后减，满足二分条件
  4. 答案具有单调性：如「求平方根」，答案本身是单调的

核心判断标准是：能否通过某个条件排除一半的搜索空间。

Q2: 二分查找中 left <= right 和 left < right 怎么选？​

答案：

写法right 初始值循环条件更新方式适用场景
左闭右闭 [l, r]length - 1left <= rightright = mid - 1精确查找目标值
左闭右开 [l, r)lengthleft < rightright = mid查找边界（lower_bound）
// 左闭右闭：搜索区间为空时停止 [left, right] 当 left > right 时为空
while (left <= right) {
  // left === right 时仍有一个元素需要检查
}

// 左闭右开：搜索区间为空时停止 [left, right) 当 left === right 时为空
while (left < right) {
  // left === right 时区间已空
}

建议：先熟练掌握左闭右闭写法，再学左闭右开写法用于找边界。

Q3: 如何用二分查找解决「在答案上二分」类型的题目？​

答案：

有些题目不是在数组中查找元素，而是在答案的范围上进行二分。核心思路是：如果答案具有单调性（答案越大越容易满足/越难满足条件），就可以二分。

// 例：木材切割 - 将 n 根木头切成 k 段等长的，求最大长度
function maxLength(woods: number[], k: number): number {
  let left = 1;
  let right = Math.max(...woods);

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

    // 以 mid 为长度能切出多少段？
    const count = woods.reduce((sum, w) => sum + Math.floor(w / mid), 0);

    if (count >= k) {
      left = mid + 1;   // 还能切更长
    } else {
      right = mid - 1;  // 切太长了，段数不够
    }
  }

  return right;
}

这类题目的特征：

  • 答案有明确的上下界
  • 给定答案可以快速验证是否可行
  • 答案具有单调性（可行/不可行的分界线）

相关链接​