二分查找

题意概述

在一个严格递增的整数数组中寻找目标值。存在时返回它的下标，不存在时返回 -1。这道题的关键不是逐个检查，而是利用有序性，每次排除一半候选元素。

输入输出示例

输入：nums = [-1, 0, 3, 5, 9, 12], target = 9
输出：4
解释：nums[4] 等于 9，下标从 0 开始。

同一个数组中，如果目标改为 2，最终搜索区间会变空，返回 -1。

解题思路

维护一个包含左右端点的区间 [left, right]。只要目标存在，它就一定在这个区间里。

1. 取中点 mid = left + Math.floor((right - left) / 2)。
2. 中点值等于目标，返回 mid。
3. 中点值小于目标，排除中点及其左侧，令 left = mid + 1。
4. 中点值大于目标，排除中点及其右侧，令 right = mid - 1。
5. 当 left > right 时，已经没有候选元素，返回 -1。

交互演示

先用「下一步」观察指针变化，再试着播放。把目标改成 2，看看查找失败时的边界。也可以输入单元素数组 9，检查三个指针重合的情况。

1 export function binarySearch(nums: readonly number[], target: number): number {2›  let left = 0;3›  let right = nums.length - 1;4  5   while (left <= right) {6     const mid = left + Math.floor((right - left) / 2);7     if (nums[mid] === target) {8       return mid;9     }10     if (nums[mid]! < target) {11       left = mid + 1;12     } else {13       right = mid - 1;14     }15   }16  17   return -1;18 }

代码实现

下面的函数可以独立使用。演示中的执行面板与此处导入同一个 TypeScript 源文件，高亮的是当前步骤对应的实际语句。

export function binarySearch(nums: readonly number[], target: number): number {
  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[mid]! < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

为什么正确

循环开始时，若目标存在，它一定在闭区间 [left, right] 内。比较中点后，由严格递增性可知：目标更大时，中点及左侧都不可能；目标更小时，中点及右侧都不可能。因此每次排除的部分不会包含答案，剩下的区间继续满足这个条件。

每轮都排除中点，区间严格缩小。最终要么找到目标，要么区间为空而返回 -1；不会遗漏答案，也不会无限循环。

复杂度

• 时间复杂度：O(log n)。每轮将候选区间缩小到大约一半。
• 额外空间复杂度：O(1)。算法本身只维护左右边界和中点。

边界情况

• 单元素数组：目标相等返回 0，不相等返回 -1。
• 目标在数组首尾：两个端点都包含在搜索区间内。
• 目标不存在：可能落在两个元素之间，也可能小于最小值或大于最大值。
• 输入必须严格递增且没有重复值。演示会报告无序、重复、小数或超出范围的输入，不会自动排序或修改它们。

教学函数也能处理空数组并返回 -1；本题演示按照非空数组的输入约束，限制为 1–24 个元素。

易错点

闭区间需要 left <= right，否则可能漏掉最后一个候选。更新为 mid + 1 或 mid - 1 才能排除已经检查过的中点；不要将闭区间的条件与半开区间的写法混用。

自测与相关题目

继续阅读 无重复字符的最长子串，观察另一种只向前移动边界的算法。