二分查找

LeetCode 704：用两轮区间示意理解二分查找与边界收缩。

LeetCode 704 简单数组

发布于 2026.10.12 约 2 分钟阅读浏览 — 次

数组
二分查找
Python
复杂度
变量

题目：704. 二分查找

在升序数组中查找 target，找到返回下标，未找到返回 -1。本题保证元素互不相同。

1. 查找过程

nums = [-1, 0, 3, 5, 9, 12]，target = 9。以下为区间示意，L、M、R 分别表示左边界、中点、右边界。

第 1 轮

代码块 Text

1
2
3
4
index:  0   1   2   3   4   5
value: -1   0   3   5   9  12
        ●───●───●───●───●───●
        L       M           R

middle = 2，nums[2] = 3 < 9，排除下标 0～2，更新 left = middle + 1，即 left = 3。

第 2 轮：只在下标 [3, 5] 中继续查找

代码块 Text

1
2
3
4
index:  3   4   5
value:  5   9  12
        ●───●───●
        L   M   R

middle = 4，nums[4] = 9，找到目标，返回下标 4。

2. 中点计算

(left + right) // 2 和 left + (right - left) // 2 两种中点写法完全等价：

\begin{aligned} \mathrm{middle} &= \mathrm{left} + \left\lfloor \frac{\mathrm{right} - \mathrm{left}}{2} \right\rfloor \\ &= \left\lfloor \frac{2\mathrm{left}}{2} + \frac{\mathrm{right} - \mathrm{left}}{2} \right\rfloor \\ &= \left\lfloor \frac{\mathrm{left} + \mathrm{right}}{2} \right\rfloor \end{aligned}

因此，Python 直接写 (left + right) // 2 即可。left + (right - left) // 2 主要用于避免定宽整数语言中的下标相加溢出；Python 整数不限固定宽度，没有这个问题。

3. Python 实现

代码块 Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search(nums, target):
    left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间 [left, right]

    while left <= right:
        middle = (left + right) // 2
        if nums[middle] > target:
            right = middle - 1  # target在左区间，所以[left, middle - 1]
        elif nums[middle] < target:
            left = middle + 1  # target在右区间，所以[middle + 1, right]
        else:
            return middle  # 数组中找到目标值，直接返回下标
    return -1  # 未找到目标值


nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary_search(nums, target))
print(binary_search(nums, 2))

# 输出：
# 4
# -1

4. 复杂度

时间复杂度：最坏为 O(log n)，每轮候选区间缩小约一半。
额外空间复杂度：O(1)，只维护固定数量的下标变量。

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。