二分搜索算法 - 数据结构与算法-学习笔记-上海佼艾

一、算法概述

二分搜索（Binary Search）是计算机科学中最基础、最重要的算法之一。它解决的核心问题是：在一个有序数组中快速定位目标元素的位置。其核心思想是分治——每次将搜索范围缩小一半，从而在对数时间内完成查找。

二分搜索的思想看似简单，但实际编码时细节极多，被称为"虽然思路很简单，但实现却很难写对"的经典算法。甚至连编程珠玑的作者Jon Bentley都曾指出，90%的专业程序员在第一次编写二分搜索时都会犯错。常见的陷阱包括：区间边界处理不当导致死循环、整数溢出、以及边界查找时逻辑混乱等。因此，深入理解二分搜索的每一种变体至关重要。

核心要点：二分搜索必须作用于有序序列；每次比较将搜索范围缩小一半；时间复杂度为 O(log n)。

1.1 生活中的二分思想

二分思想在日常生活中非常普遍。例如：猜数字游戏中，甲在心里想一个1~100之间的整数，乙来猜。乙每次猜一个数，甲告诉乙"猜大了"或"猜小了"。如果乙采用二分策略——每次都猜中间的数字，那么最多只需要猜7次（因为 2^7 = 128 > 100）就一定能猜中。这种每次排除一半可能性的策略，就是二分搜索的精髓。

┌─────────────────────────────────────────┐ │ 猜数字游戏的二分过程 │ │ │ │ 目标: 37 范围: [1, 100] │ │ │ │ 第1步: 猜 50 → "猜大了" → 范围缩小到 [1, 49] │ │ 第2步: 猜 25 → "猜小了" → 范围缩小到 [26, 49] │ │ 第3步: 猜 37 → "猜对了！" │ │ │ │ 每次排除一半，log₂(100) ≈ 7 次内必中 │ └─────────────────────────────────────────┘

1.2 前置条件

使用二分搜索前必须满足以下两个条件：

有序性：数组必须是单调递增或单调递减的。如果数组无序，必须先排序再使用二分搜索（但排序后可能丢失原始索引信息）。
随机访问：数据结构必须支持 O(1) 的随机访问。数组满足此条件，但链表（LinkedList）不满足——在链表上执行二分搜索的时间复杂度会退化为 O(n log n)。

二、基本实现

二分搜索的边界定义方式直接决定了代码的写法。最常见的两种区间定义是左闭右闭 [left, right] 和 左闭右开 [left, right)。初学者往往因为混淆这两种写法而出错。下面分别给出两种实现的详细分析。

2.1 左闭右闭 [left, right]

这是最直观的写法。区间 [left, right] 表示搜索范围包含 left 和 right 两个端点。循环条件为 left <= right，因为当 left == right 时，区间内还有一个元素需要检查。

def binary_search_closed(nums, target):
    """左闭右闭区间 [left, right]"""
    left, right = 0, len(nums) - 1

    while left <= right:                      # left == right 时区间仍有效
        mid = left + (right - left) // 2    # 防止整数溢出

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1                   # target 在右半部分
        else:
            right = mid - 1                  # target 在左半部分

    return -1                                 # 未找到

关键点在于：当 nums[mid] < target 时，我们已确认 nums[mid] 不是目标值，所以将左边界更新为 mid + 1；同理，当 nums[mid] > target 时，将右边界更新为 mid - 1。这样可以确保搜索区间不断缩小，避免死循环。

2.2 左闭右开 [left, right)

左闭右开是另一种常用写法，也是 Python 语言中 range 函数的惯用区间表示法。区间 [left, right) 包含 left 但不包含 right。循环条件为 left < right，因为当 left == right 时区间已为空。

def binary_search_half_open(nums, target):
    """左闭右开区间 [left, right)"""
    left, right = 0, len(nums)

    while left < right:                       # left == right 时区间为空
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1                   # target 在右半部分 [mid+1, right)
        else:
            right = mid                        # target 在左半部分 [left, mid)

    return -1

注意两种写法的关键区别：左闭右开时，right 的初始值是 len(nums) 而不是 len(nums)-1；更新右边界时 right = mid 而不是 mid - 1。这是因为右边界是开区间，mid 本身已被排除但 right 指向的是开区间边界。

[left, right] 左闭右闭

right = len(nums) - 1

循环条件: left <= right

左移: left = mid + 1

右移: right = mid - 1

[left, right) 左闭右开

right = len(nums)

循环条件: left < right

左移: left = mid + 1

右移: right = mid

2.3 整数溢出防范

初学者常写的中间位置计算方式是 (left + right) // 2。当 left 和 right 都非常大时（例如接近 2^31 - 1），left + right 可能超出 int 类型的表示范围，导致整数溢出。在 C++ / Java 等语言中这会导致严重的 bug。

安全的写法有以下两种：

# 方法一：减法防溢出（推荐）
mid = left + (right - left) // 2

# 方法二：无符号右移（Java 特有）
// int mid = (left + right) >>> 1;

# Python 中整数是无限精度的，不会溢出
# 但养成好习惯总是有益的

Python 的 int 是无限精度类型，不会出现整数溢出。但如果你将来要写 C++ 或 Java，养成使用 left + (right - left) // 2 的习惯是很好的。

三、二分搜索的变体：边界查找

实际问题中，我们往往不是简单查找一个值是否存在，而是需要查找满足某种条件的边界位置。当数组中存在重复元素时，标准的二分搜索只能返回任意一个匹配的位置，但无法控制返回的是第一个还是最后一个。以下是四种最常见的边界查找变体。

3.1 查找第一个等于 target 的位置

def find_first_equal(nums, target):
    """查找第一个等于 target 的元素下标"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid                      # nums[mid] >= target 时收缩右边界

    # left == right 是第一个 >= target 的位置
    if left < len(nums) and nums[left] == target:
        return left
    return -1

这里的关键技巧：当 nums[mid] == target 时，我们不直接返回，而是将右边界左移（right = mid），继续在左半部分查找，直到找到第一个出现的位置。这种"收缩右边界继续搜索"的技巧是边界查找的核心模式。

3.2 查找最后一个等于 target 的位置

def find_last_equal(nums, target):
    """查找最后一个等于 target 的元素下标"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > target:
            right = mid
        else:
            left = mid + 1                 # nums[mid] <= target 时收缩左边界

    # left 是第一个 > target 的位置，left-1 是最后一个 <= target 的位置
    if left > 0 and nums[left - 1] == target:
        return left - 1
    return -1

查找最后一个等于 target 的位置，可以转化为：找到第一个大于 target 的位置，然后减 1。当 nums[mid] <= target 时收缩左边界（left = mid + 1），最终 left 指向第一个大于 target 的位置。

3.3 查找最后一个小于 target 的位置

def find_last_less(nums, target):
    """查找最后一个小于 target 的元素下标"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left - 1    # left 是第一个 >= target 的位置

3.4 查找第一个大于 target 的位置

def find_first_greater(nums, target):
    """查找第一个大于 target 的元素下标"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left     # 可能返回 len(nums)，表示不存在大于 target 的数

记忆口诀：查找"第一个 XX"用 right = mid 收缩上界；查找"最后一个 XX"用 left = mid + 1 收缩下界。核心思路是：在判断条件中只使用 < 和 >= 或 <= 和 > 的组合，避免使用 == 分支。

四、时间复杂度分析

4.1 O(log n) 的推导

在长度为 n 的有序数组中执行二分搜索，每次比较都会将搜索范围缩小一半。假设经过 k 次比较后，搜索范围缩小到只剩 1 个元素，则满足：

n / 2^k = 1
=> n = 2^k
=> k = log₂(n)

因此二分搜索的时间复杂度为 O(log n)。这里的对数底数为 2，但在大 O 表示法中，对数底数被视为常数因子，通常简写为 O(log n)。

4.2 与线性搜索的对比

为了直观理解 O(log n) 的威力，可以比较不同规模下二分搜索与线性搜索的最大比较次数：

数组规模 n	线性搜索 O(n)	二分搜索 O(log n)	性能差距
10	10 次	4 次	2.5x
100	100 次	7 次	14x
1,000	1,000 次	10 次	100x
10,000	10,000 次	14 次	714x
1,000,000	1,000,000 次	20 次	50,000x
1,000,000,000	10 亿次	30 次	33,000,000x

当 n = 10 亿时，线性搜索需要最多 10 亿次比较，而二分搜索只需要 30 次——这就是对数算法的惊人效率。

思考：如果数组长度为 2^63（约 92 亿亿），二分搜索最多只需要 63 次比较就能找到目标！这就是为什么说"二分搜索是指数级速度的算法"。

五、Python bisect 模块

Python 标准库提供了 bisect 模块，封装了二分搜索的核心操作。在实际开发中，应优先使用标准库而非手写二分搜索，因为标准库经过充分测试且性能更高。

5.1 核心函数

函数	功能	对应手写算法
bisect_left(a, x)	返回第一个 >= x 的位置	find_first_equal / find_first_greater_equal
bisect_right(a, x)	返回第一个 > x 的位置	find_first_greater
insort_left(a, x)	在有序序列中插入 x，保持有序（插在相等元素左边）	bisect_left + list.insert
insort_right(a, x)	在有序序列中插入 x，保持有序（插在相等元素右边）	bisect_right + list.insert

import bisect

arr = [1, 3, 5, 5, 5, 7, 9]

# bisect_left: 返回第一个 >= 5 的位置
idx = bisect.bisect_left(arr, 5)           # idx = 2
print(idx)                               # 输出: 2

# bisect_right: 返回第一个 > 5 的位置
idx = bisect.bisect_right(arr, 5)          # idx = 5
print(idx)                               # 输出: 5

# 用 bisect_left 和 bisect_right 计算元素出现次数
count = bisect.bisect_right(arr, 5) - bisect.bisect_left(arr, 5)
print(count)                             # 输出: 3

# insort: 插入元素并保持有序
bisect.insort_left(arr, 4)
print(arr)                               # 输出: [1, 3, 4, 5, 5, 5, 7, 9]

5.2 实用技巧

利用 bisect 模块可以实现很多常用功能：

import bisect

# 1. 将百分制分数映射为等级
def grade(score, breakpoints=[60, 70, 80, 90],
          grades='FDCBA'):
    idx = bisect.bisect_right(breakpoints, score)
    return grades[idx]

for s in [33, 60, 75, 88, 95]:
    print(f"{s}分 → {grade(s)}")
# 输出: 33分 → F, 60分 → D, 75分 → C, 88分 → B, 95分 → A

# 2. 查找距离目标最近的元素
arr = [1, 4, 6, 8, 10]
target = 7
pos = bisect.bisect_left(arr, target)
if pos == 0:
    nearest = arr[0]
elif pos == len(arr):
    nearest = arr[-1]
else:
    if arr[pos] - target < target - arr[pos - 1]:
        nearest = arr[pos]
    else:
        nearest = arr[pos - 1]
print(nearest)                            # 输出: 6

最佳实践：在竞赛或生产环境中，只要涉及有序数组的查找或插入操作，优先考虑 bisect 模块。它比手写代码更可靠、更高效（底层用 C 实现）。

六、二分搜索的应用场景

6.1 旋转数组搜索

给定一个升序排列的数组在某个未知点进行了旋转（例如 [4,5,6,7,0,1,2]），要求以 O(log n) 时间查找目标值。这是二分搜索的经典变体问题（LeetCode 33）。

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid

        # 判断 mid 落在左半部分还是右半部分
        if nums[left] <= nums[mid]:        # 左半部分是有序的
            if nums[left] <= target < nums[mid]:
                right = mid - 1              # target 在左半部分
            else:
                left = mid + 1               # target 在右半部分
        else:                                 # 右半部分是有序的
            if nums[mid] < target <= nums[right]:
                left = mid + 1               # target 在右半部分
            else:
                right = mid - 1              # target 在左半部分

    return -1

核心思路：虽然整个数组是旋转的，但每次二分后，左半部分和右半部分中至少有一部分是完全有序的。利用这一特性，我们可以判断 target 是否在有序的那部分中，从而缩小搜索范围。

进阶思考：如果旋转数组中存在重复元素（LeetCode 81），当 nums[left] == nums[mid] == nums[right] 时，无法判断哪侧有序，此时只能将 left 和 right 各收缩一步，最坏时间复杂度退化为 O(n)。

6.2 二分答案

二分搜索不仅可以用于查找元素，还可以用于在解空间中搜索最优解。当问题具有单调性（即某个判断条件随答案单调变化）时，可以将原问题转化为判定问题，并用二分搜索求解。这就是"二分答案"算法，它也是算法竞赛中的核心技巧之一。

# 例题：在 D 天内送达包裹的能力（LeetCode 1011）
# 给定包裹重量数组 weights 和天数 D，求最低的运载能力
def ship_within_days(weights, D):
    def can_ship(capacity):
        """判断是否能在 D 天内运送完所有包裹"""
        days = 1
        cur = 0
        for w in weights:
            if cur + w > capacity:
                days += 1
                cur = 0
            cur += w
        return days <= D

    # 二分搜索答案空间：最低运力 = max(weights)，最高 = sum(weights)
    left, right = max(weights), sum(weights)

    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid                    # mid 可行，尝试更小的容量
        else:
            left = mid + 1                # mid 不可行，需要更大的容量

    return left

二分答案的关键步骤：

确定答案的取值范围（解空间），并验证取值上的单调性
设计一个高效（通常 O(n) 或 O(n log n)）的判定函数，检查给定值是否可行
在解空间上执行二分搜索，找到满足条件的最小/最大值

6.3 求平方根

在不使用 sqrt 函数的前提下求整数 x 的平方根（LeetCode 69）。这是一个典型的二分答案问题，解空间为 [0, x]。

def my_sqrt(x):
    if x < 2:
        return x

    left, right = 0, x
    while left <= right:
        mid = left + (right - left) // 2
        mid_sq = mid * mid

        if mid_sq == x:
            return mid
        elif mid_sq < x:
            left = mid + 1
        else:
            right = mid - 1

    return right     # 返回整数部分

6.4 峰值查找

峰值元素是指其值大于左右相邻值的元素。在一个不存在相等相邻元素的数组中，查找任意一个峰值（LeetCode 162）。

def find_peak_element(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[mid + 1]:
            # 峰值在左半部分（包含 mid）
            right = mid
        else:
            # 峰值在右半部分（不包含 mid）
            left = mid + 1

    return left     # left == right 即为峰值位置

本题的巧妙之处在于利用二分搜索的局部比较——比较 nums[mid] 和 nums[mid+1]，确定峰值的可能方向。因为题目保证相邻元素不相等，所以这种二分策略总是有效的。

二分搜索的应用远不止在数组中查找元素。只要问题的解空间是单调的（或是单峰的），就可以考虑用二分搜索来加速求解。常见的应用场景包括：求最值问题的可行解、求方程的解、在数据流中查找分位数、三维重建中的距离场计算等。

七、常见错误与注意事项

7.1 五大常见错误

错误1：死循环

在左闭右闭写法中，如果更新边界时写成 left = mid 或 right = mid，当 left 和 right 相邻时可能陷入死循环。例如 left=3, right=4, mid=3，如果 nums[3] != target 且更新 left=3，则区间始终无法缩小。

错误2：初始边界错误

使用左闭右闭时 right 应初始化为 len(nums)-1，左闭右开时初始化为 len(nums)。混淆这两个初始值会导致漏搜末尾元素或越界。

错误3：循环条件错误

左闭右闭用 left < right（漏掉 left==right 时的最后一个元素）；左闭右开用 left <= right（多余比较且可能死循环）。

错误4：整数溢出

在 C++/Java 中使用 (left+right)/2 可能导致整数溢出。Python 中无此问题，但养成好习惯仍很重要。

错误5：边界查找时混淆逻辑

查找"第一个大于"与"第一个大于等于"时，判断条件仅差一个等号，容易搞混。建议背诵前面表格中的基本模式。

7.2 二分搜索的选择指南

场景	推荐的实现方式
简单查找元素是否存在	bisect_left + 判断返回值
查找第一个/最后一个等于某值	bisect_left / bisect_right
查找第一个大于等于某值	bisect_left
查找第一个大于某值	bisect_right
在有序数组中插入并保持有序	insort_left / insort_right
二分答案（算法竞赛）	手写 left < right 模板
旋转数组搜索	手写特殊逻辑
浮点数二分	手写，用 eps 控制精度或固定迭代次数

7.3 浮点数二分

当解空间是浮点数时，不能简单地使用 left < right，需要引入精度控制：

def float_binary_search(l, r, target, eps=1e-7):
    """浮点数二分搜索示例：求立方根"""
    while r - l > eps:
        mid = (l + r) / 2
        if mid * mid * mid < target:
            l = mid
        else:
            r = mid
    return l

技巧：在算法竞赛中，一个常用的做法是固定迭代次数（如 100 次），而不是使用 while 循环的 eps 判断。100 次迭代可以将精度提高到 2^(-100)，远超实际需求。

八、核心要点总结

二分搜索算法总结

基本原理：有序数组中的分治查找，每次排除一半元素，时间复杂度 O(log n)
两种区间写法：左闭右闭 [left, right]（循环条件 left <= right）和左闭右开 [left, right)（循环条件 left < right），务必保持一致
整数溢出防范：使用 mid = left + (right - left) // 2 替代 (left + right) // 2
边界查找四兄弟：第一个等于、最后一个等于、最后一个小于、第一个大于——掌握 bisect_left 和 bisect_right 即可通吃
Python bisect 模块：bisect_left / bisect_right / insort_left / insort_right，开发中优先使用
二分答案：当问题具有单调性时，将最优化问题转化为判定问题，在解空间上二分
经典应用：旋转数组搜索、平方根计算、峰值查找、D天内送达包裹、求方程的根
常见陷阱：死循环（更新边界未正确 +1/-1）、初始边界错误、循环条件错误、整数溢出
浮点数二分：使用精度控制 eps 或固定迭代次数（如 100 次）

一句话记忆：二分搜索的核心不是"在有序数组中找目标值"，而是"在单调的解空间中搜索分割点"——一旦理解了这点，你就能将二分搜索应用到远远超出数组查找的广阔领域。