704. 二分查找

在算法基础里，「有序序列上的查找」几乎总会落到二分：每次把搜索范围砍掉一半，用对数级比较换线性扫描。对应到力扣，便是经典的 704. 二分查找。

题目本身不难，却把区间开闭、中点计算、边界更新这几处细节捆在一起——写对一次，后面大量「在答案上二分」的题都会轻松很多。

题目

704.二分查找

给定一个 $n$ 个元素升序的整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 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 中

约束要点： 元素互不相同；$n \in [1, 10^4]$；元素落在 $[-9999, 9999]$。

核心思路

数组已升序，任意中点 mid 都能把区间劈成两段：

• nums[mid] == target：找到，直接返回 mid
• nums[mid] < target：目标只可能在右半段
• nums[mid] > target：目标只可能在左半段

因此维护一个不断收缩的候选区间即可。下文采用闭区间 [left, right]：循环条件为 left <= right，落空时返回 $-1$。

每次比较后区间长度至少减半，比较次数为 $O(\log n)$；除循环变量外无额外与 $n$ 相关的存储，辅助空间 $O(1)$。

下面用闭区间模板演示题目示例。建议先点「下一步」：每一轮拆成两拍——先算出 mid 并和 target 比较，再丢掉不可能的那半边并更新 left / right。格子上方的 left / mid / right 标明当前边界；红色半透明是本步即将排除的部分。

要找的数9

切换示例 示例 1：找 9（能找到）示例 2：找 2（找不到）

目标：在升序数组里查找 9

闭区间 [left, right] = [0, 5]。点「下一步」开始第 1 轮。

当前候选区间 [left, right] = [0, 5] （一共 6 个数）

left

-1

下标 0

 

0

下标 1

 

3

下标 2

 

5

下标 3

 

9

下标 4

right

12

下标 5

left 左边界 mid 中点 right 右边界 还在查的区间 本步要丢掉 已经排除 命中

步骤记录（最新在上）

1. 准备：查找 9，区间 [0, 5]

闭区间实现

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 1. 闭区间 [left, right]，初始覆盖整个数组
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        // 2. 区间非空时继续；空则说明不存在
        while (left <= right) {
            // 3. 防溢出的中点：等价于 (left + right) / 2
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                // 4. mid 已排除，右半从 mid + 1 起
                left = mid + 1;
            } else {
                // 5. mid 已排除，左半到 mid - 1 止
                right = mid - 1;
            }
        }
        return -1;
    }
};

Java

class Solution {
    public int search(int[] nums, int target) {
        // 1. 闭区间 [left, right]，初始覆盖整个数组
        int left = 0;
        int right = nums.length - 1;

        // 2. 区间非空时继续；空则说明不存在
        while (left <= right) {
            // 3. 防溢出的中点：等价于 (left + right) / 2
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                // 4. mid 已排除，右半从 mid + 1 起
                left = mid + 1;
            } else {
                // 5. mid 已排除，左半到 mid - 1 止
                right = mid - 1;
            }
        }
        return -1;
    }
}

Python

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        # 1. 闭区间 [left, right]，初始覆盖整个数组
        left, right = 0, len(nums) - 1

        # 2. 区间非空时继续；空则说明不存在
        while left <= right:
            # 3. 防溢出的中点（Python int 任意精度，仍保持统一写法）
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                # 4. mid 已排除，右半从 mid + 1 起
                left = mid + 1
            else:
                # 5. mid 已排除，左半到 mid - 1 止
                right = mid - 1
        return -1

Go

func search(nums []int, target int) int {
	// 1. 闭区间 [left, right]，初始覆盖整个数组
	left, right := 0, len(nums)-1

	// 2. 区间非空时继续；空则说明不存在
	for left <= right {
		// 3. 防溢出的中点：等价于 (left + right) / 2
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			// 4. mid 已排除，右半从 mid + 1 起
			left = mid + 1
		} else {
			// 5. mid 已排除，左半到 mid - 1 止
			right = mid - 1
		}
	}
	return -1
}

步骤与代码一一对应：

1. left、right 取闭区间两端，覆盖全体下标；
2. left <= right 表示仍有候选元素；一旦 left > right，区间为空；
3. mid = left + (right - left) / 2，避免 left + right 溢出；
4. nums[mid] < target 时丢弃左半（含 mid），令 left = mid + 1；
5. nums[mid] > target 时丢弃右半（含 mid），令 right = mid - 1。

另一种常见写法：左闭右开

若坚持区间为 [left, right)，则循环条件改为 left < right，且右边界初值为 n。更新规则也要跟着变：

• nums[mid] < target → left = mid + 1（mid 仍排除）
• nums[mid] > target → right = mid（右开，mid 本身不进入下一轮）

两种模板都能通过本题；关键是区间定义与更新规则自洽，不要混用。

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 1. 左闭右开 [left, right)
        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;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                // 2. 右开区间：right 收到 mid，不再包含 mid
                right = mid;
            }
        }
        return -1;
    }
};

Java

class Solution {
    public int search(int[] nums, int target) {
        // 1. 左闭右开 [left, right)
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                // 2. 右开区间：right 收到 mid，不再包含 mid
                right = mid;
            }
        }
        return -1;
    }
}

Python

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        # 1. 左闭右开 [left, right)
        left, right = 0, len(nums)

        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                # 2. 右开区间：right 收到 mid，不再包含 mid
                right = mid
        return -1

Go

func search(nums []int, target int) int {
	// 1. 左闭右开 [left, right)
	left, right := 0, len(nums)

	for left < right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			left = mid + 1
		} else {
			// 2. 右开区间：right 收到 mid，不再包含 mid
			right = mid
		}
	}
	return -1
}

细节与易错点

中点溢出

在部分语言中，left + right 可能超出整型上限。统一写成：

$$\mathrm{mid} = \mathrm{left} + \left\lfloor\frac{\mathrm{right}-\mathrm{left}}{2}\right\rfloor$$

语义与 $(\mathrm{left}+\mathrm{right})/2$ 相同，数值更安全。

区间与循环条件必须配套

区间	初值	循环条件	nums[mid] > target 时
$[L,R]$	$R = n-1$	left <= right	right = mid - 1
$[L,R)$	$R = n$	left < right	right = mid

混用会导致漏查或死循环。例如闭区间却写 right = mid，在 nums[mid] > target 且 mid == right 时区间不收缩。

相等分支的位置

本题元素唯一，找到即可返回。若题目要求「第一个 / 最后一个等于 target 的位置」，相等时不能立刻返回，而要继续向左或向右收缩——那是「在答案上二分」的变体，模板会不同。

复杂度

• 时间：$O(\log n)$。每次迭代至少排除一半元素，至多约 $\lfloor\log_2 n\rfloor + 1$ 次比较。
• 空间：$O(1)$。仅使用常数个下标变量；递归写法则为 $O(\log n)$ 栈空间，本题采用迭代。

与「算法评估」一文中的对数增长一致：规模每扩大一倍，额外比较约增加一次。