704. 二分查找

题目

力扣题目 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

考察内容

• 有序数组的随机访问
• 二分查找的区间定义与循环不变量
• 边界收缩以及循环终止条件
• 防止中点计算发生整数溢出
• 时间复杂度从 $O(n)$ 优化到 $O(\log n)$

解题思路

二分查找利用数组已经升序排列这一条件，每轮选择待查区间的中点 mid，并比较 nums[mid] 与 target：

1. nums[mid] == target：找到目标，返回 mid；
2. nums[mid] < target：目标只可能在右半部分；
3. nums[mid] > target：目标只可能在左半部分。

每轮都能排除大约一半的数据，因此最多只需要进行 $\log_2 n$ 轮查找。

左闭右闭区间 [left, right]

循环过程中，left 和 right 指向的位置都属于待查区间。

• 初始区间：left = 0，right = nums.size() - 1
• 循环条件：left <= right
• 去掉左半部分：left = mid + 1
• 去掉右半部分：right = mid - 1

之所以要使用 mid + 1 和 mid - 1，是因为 mid 已经比较过，可以从下一轮的待查区间中排除。

左闭右开区间 [left, right)

left 属于待查区间，而 right 不属于待查区间。

• 初始区间：left = 0，right = nums.size()
• 循环条件：left < right
• 去掉左半部分：left = mid + 1
• 去掉右半部分：right = mid

此时不能写成 right = mid - 1，因为右边界本来就取不到；将 right 更新为 mid 已经排除了中点。

两种写法都正确，关键是从初始化、循环条件到边界更新始终遵守同一种区间定义，不要混用。

执行过程

以 nums = [-1, 0, 3, 5, 9, 12]、target = 9 为例，采用左闭右闭区间：

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

代码演示

// 左闭右闭区间写法，left，right 都属于待查区
int search(std::vector<int>& nums, int target) {
    int left  = 0;
    int right = static_cast<int>(nums.size()) - 1;

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

// 左闭右开区间写法，right 不属于待查区间
int search2(std::vector<int>& nums, int target) {
    int left  = 0;
    int right = static_cast<int>(nums.size());

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

易错点

• 忘记数组必须有序：普通二分查找只能直接用于单调序列。
• 混用两种区间定义：例如初始化为 right = nums.size()，却使用 left <= right，可能导致数组越界。
• 边界没有排除 mid：在左闭右闭写法中若写成 left = mid 或 right = mid，某些情况下区间不会缩小，从而造成死循环。
• 中点计算溢出：推荐使用 left + (right - left) / 2，避免 left + right 超出整数范围。
• 空数组时的无符号数问题：nums.size() 返回无符号类型。应先转换为有符号下标类型再减 1，避免 0 - 1 在无符号类型中下溢。
• 题目要求返回原始下标时不要随意排序：对无序数组先排序会改变元素下标，需要额外保存原始位置。

总结

二分查找的核心不是背诵模板，而是维护一个明确的待查区间：

1. 根据区间定义设置左右边界；
2. 每轮检查中点；
3. 排除已经确认不可能包含答案的半个区间；
4. 保证新区间严格缩小，直到找到目标或区间为空。

对于本题，左右边界只需要常数级变量，所以空间复杂度为 $O(1)$；待查范围每轮减半，所以时间复杂度为 $O(\log n)$。

相关题目

• 35. 搜索插入位置
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 69. x 的平方根
• 367. 有效的完全平方数
• 153. 寻找旋转排序数组中的最小值
• 33. 搜索旋转排序数组
• 74. 搜索二维矩阵