Q704 二分查找

题目：给定一个升序整数数组 nums 和目标值 target。如果目标值存在，返回它的下标；否则返回 -1。题目保证数组中的元素不重复。

1 简要回答

二分查找适用于有序数组。每次比较中间元素与目标值，根据大小关系排除一半搜索范围，直到找到目标值或区间为空。

真正容易出错的地方不是算法思想，而是区间边界。写代码前必须先确定搜索区间是 [left, right] 还是 [left, right)，并让循环条件与边界更新始终遵守这个定义，这就是循环不变量。

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

2 核心思想

设数组为：

1
2
3

下标：  0   1   2   3   4   5
数组： -1   0   3   5   9  12
目标： target = 9

查找过程：

1
2
3
4
5

第 1 次：[0, 5]，mid = 2，nums[2] = 3 < 9
         排除下标 0～2，下一轮搜索 [3, 5]

第 2 次：[3, 5]，mid = 4，nums[4] = 9
         找到目标，返回下标 4

每次至少排除当前区间的一半，所以最多查找约 $\log_2 n$ 次。

3 什么是循环不变量

在循环开始、执行过程中和结束时，搜索目标所在区间的定义始终不变。

例如选择左闭右闭区间 [left, right] 后：

• left 指向的元素在搜索范围内。
• right 指向的元素也在搜索范围内。
• 每次更新后，新的区间仍然必须是左闭右闭。

因此不能一会儿按照闭区间写 right = mid - 1，一会儿又按照开区间写 right = mid。

4 size 与 size - 1 的区别

假设数组中有 6 个元素：

1
2
3

元素个数 size = 6
有效下标：0、1、2、3、4、5
最后一个有效下标：size - 1 = 5

因此，size 表示的是元素个数，而 size - 1 才是最后一个元素的下标。

4.1 为什么左闭右闭使用 size - 1

左闭右闭区间 [left, right] 包含 right：

1
2

数组有效下标：[0, 5]
搜索区间：    [0, 5]

所以 right 必须指向最后一个有效元素：

1

int right = static_cast<int>(nums.size()) - 1;

如果这里写成 right = nums.size()，就会把不存在的 nums[6] 也放进搜索范围，可能造成越界。

4.2 为什么左闭右开使用 size

左闭右开区间 [left, right) 不包含 right：

1
2

数组有效下标：[0, 5]
搜索区间：    [0, 6)

虽然 right = 6，但右端点不参与搜索，真正包含的仍然是下标 0～5：

1

int right = static_cast<int>(nums.size());

记忆方法：

• 右边界包含在区间里：它必须是有效下标，所以使用 size - 1。
• 右边界不包含在区间里：它可以指向末尾元素的后一个位置，所以使用 size。

5 写法一：左闭右闭区间

因为左右端点都有效，所以：

• 初始化：right = nums.size() - 1
• 循环条件：left <= right
• 去左半边：right = mid - 1
• 去右半边：left = mid + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        // 搜索区间始终是 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;   // 下一轮：[mid + 1, right]
            } else {
                right = mid - 1;  // 下一轮：[left, mid - 1]
            }
        }

        return -1;
    }
};

初学时可以先固定使用左闭右闭写法。循环条件和边界更新比较对称：<=、mid + 1、mid - 1。

6 写法二：左闭右开区间

因为右端点不在搜索范围内，所以：

• 初始化：right = nums.size()
• 循环条件：left < right
• 去左半边：right = mid
• 去右半边：left = mid + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size());

        // 搜索区间始终是 [left, right)
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;  // 下一轮：[mid + 1, right)
            } else {
                right = mid;     // 下一轮：[left, mid)
            }
        }

        return -1;
    }
};

7 两种写法对照

不要混用：[left, right] 配套的是 left <= right 和 right = mid - 1；[left, right) 配套的是 left < right 和 right = mid。混用会漏查元素、越界或造成死循环。

8 为什么这样计算 mid

推荐写法：

1

int mid = left + (right - left) / 2;

不推荐：

1

int mid = (left + right) / 2;

数学结果相同，但当 left 和 right 很大时，left + right 可能发生整数溢出。先计算差值更加安全。

9 二分查找的真正前提

基础二分查找需要搜索空间具有单调性。在本题中表现为数组升序，因此比较 nums[mid] 与 target 后能够确定目标只可能位于哪一半。

数组中有重复元素还能二分吗？可以。重复元素不会让普通二分查找失效，但返回的可能是任意一个匹配位置。如果题目要求第一个或最后一个匹配位置，就需要使用边界二分（lower_bound / upper_bound）。

9.1 常见应用

• 在有序数组中查找某个值。
• 查找第一个大于等于目标值的位置，即 lower_bound。
• 查找最后一个小于等于目标值的位置。
• 对具有单调性的答案范围进行"二分答案"。

相关练习：LeetCode 35 搜索插入位置、LeetCode 34 查找元素首末位置、LeetCode 69 x 的平方根、LeetCode 367 有效的完全平方数。

10 空数组的细节

vector::size() 返回无符号整数。如果直接计算 nums.size() - 1，空数组时会发生无符号下溢。因此左闭右闭版本先转换为有符号整数：

1

int right = static_cast<int>(nums.size()) - 1;

11 易错点

• 没先定义搜索区间，就开始拼凑边界代码。
• 左闭右闭写成 while (left < right)，漏掉只剩一个元素的情况。
• 左闭右开写成 right = mid - 1，额外漏掉一个元素。
• 写成 left = mid 或 right = mid 时没有证明区间一定缩小，可能死循环。
• 使用 (left + right) / 2，忽略整数溢出风险。
• 看到重复元素就认为不能二分；真正的问题是返回哪一个匹配位置。