python必背源代码二分查找代码

Leo
Leo
发布时间:2026-11-20 | 10人浏览过
原创

本文提供Python必背源代码二分查找代码的标准循环模板、递归实现与处理重复元素的左右边界变体。包含完整的算法执行逻辑、推导流程图、易错边界防坑指南与内置bisect模块对比,帮助开发者快速掌握对数级高效检索。

python必背源代码二分查找代码
二分查找(Binary Search)是在有序序列中快速定位目标元素的经典算法。其核心思路是通过每次比对区间中点,排除一半无效区间,将搜索时间复杂度从线性扫描的 O(n) 直接降至对数级别的 O(log n)。在日常开发与算法面试中,二分查找是必须熟练背诵并能随时手写的基本功。本文直接提供 Python 标准循环版必背模板、递归实现、处理重复元素的左右边界查找变体,以及 Python 内置 bisect 模块的最佳实践,并梳理核心判断依据与避坑要点。

一、二分查找的前提条件与基本原理

二分查找之所以能够实现高效检索,依赖于一个严苛的前提条件:数据必须是有序的,且底层数据结构必须支持 O(1) 的随机访问(例如 Python 的列表 list)。如果要在无序序列或链表上检索,二分查找便不成立。

算法在执行时维护两个指针:left 指向当前搜索区间的起始索引,right 指向结束索引。每一次迭代计算中点索引 mid,并对比中点元素 nums[mid] 与目标值 target:

  • 若 nums[mid] == target:已命中目标,直接返回当前下标 mid。
  • 若 nums[mid] < target:由于数组升序排列,中点左侧所有元素都小于 target,目标只能存在于右半侧。因此更新左界 left = mid + 1。
  • 若 nums[mid] > target:中点右侧所有元素都大于 target,目标只能存在于左半侧。因此更新右界 right = mid - 1。
python必背源代码二分查找代码
图 1:二分查找核心推导步骤(以有序数组检索 target = 23 为例的两轮折半推导演示)

二、最经典必背源代码:闭区间迭代实现

在实际编写和面试场景中,最不容易出错、也是各技术团队普遍认可的标准写法是闭区间迭代法(即区间定义始终为 [left, right])。以下是必须牢记的完整源代码实现:

binary_search.py(标准闭区间模板) Python 3.x
def binary_search(nums: list[int], target: int) -> int:
    """
    在升序列表 nums 中二分查找目标值 target
    :param nums: 严格升序排列的整数列表
    :param target: 待查找的目标数值
    :return: 若找到返回对应下标,未找到返回 -1
    """
    left = 0
    right = len(nums) - 1  # 闭区间 [0, len(nums) - 1]

    while left <= right:   # 当 left == right 时,区间内还有一个元素需要检查
        # 防止整型溢出的标准写法(等价于 (left + right) // 2)
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1   # 目标在右侧,排除 mid 后的新区见为 [mid + 1, right]
        else:
            right = mid - 1  # 目标在左侧,排除 mid 后的新区间为 [left, mid - 1]

    return -1  # 循环结束未找到目标,返回 -1

完整运行示例与输出验证

可以在任意 Python 3 环境下新建脚本并执行以下测试代码:

test_binary_search.py 测试用例
if __name__ == "__main__":
    test_cases = [
        ([2, 5, 8, 12, 16, 23, 38], 23),  # 正常命中
        ([2, 5, 8, 12, 16, 23, 38], 2),   # 命中首个元素
        ([2, 5, 8, 12, 16, 23, 38], 38),  # 命中末尾元素
        ([2, 5, 8, 12, 16, 23, 38], 15),  # 列表中不存在的目标
    ]

    for nums, target in test_cases:
        res = binary_search(nums, target)
        print(f"在数组 {nums} 中查找 {target} -> 索引结果: {res}")
控制台运行结果示例
在数组 [2, 5, 8, 12, 16, 23, 38] 中查找 23 -> 索引结果: 5
在数组 [2, 5, 8, 12, 16, 23, 38] 中查找 2 -> 索引结果: 0
在数组 [2, 5, 8, 12, 16, 23, 38] 中查找 38 -> 索引结果: 6
在数组 [2, 5, 8, 12, 16, 23, 38] 中查找 15 -> 索引结果: -1

三个关键细节的原因解析

  • 为什么循环条件是 left <= right 而非 left < right?
    因为初始设定 right = len(nums) - 1 决定了搜索范围是闭区间 [left, right]。当 left == right 时,区间如 [3, 3] 并非空集,依然包含下标 3 这个元素需要验证。如果漏掉等号,处于该位置的目标将被直接忽略。
  • 为什么边界移动必须是 mid + 1 和 mid - 1?
    因为在条件分支中,nums[mid] == target 已经被判断并排除,当前 mid 绝不可能是目标。下一轮必须从排除中点后的新区间开始。如果不加减 1,当 left 和 right 相邻时会导致区间永远无法缩小,陷入死循环。
  • 中点计算为什么写成 left + (right - left) // 2?
    在 C/C++ 或 Java 中,直接写 (left + right) // 2 当两者数值很大时可能导致整型溢出。虽然 Python 具有原生任意精度大整型支持,但养成规范的算法书写习惯有助于跨语言保持一致性与严谨性。
python必背源代码二分查找代码
图 2:标准迭代二分查找算法执行流程与状态决策模型

三、必背变体一:递归实现版本

二分查找本质是分治(Divide and Conquer)思想的典型体现:把规模为 n 的问题分解为规模为 n/2 的同类子问题。在教学考核或分治题目中,面试官经常要求给出递归实现。

binary_search_recursive.py Python 3.x
def binary_search_recursive(nums: list[int], target: int, left: int = 0, right: int = None) -> int:
    """
    二分查找的递归实现
    """
    if right is None:
        right = len(nums) - 1

    # 递归终止基线条件:搜索区间已失效
    if left > right:
        return -1

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

    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        # 目标在右半区,递归缩小左界
        return binary_search_recursive(nums, target, mid + 1, right)
    else:
        # 目标在左半区,递归缩小右界
        return binary_search_recursive(nums, target, left, mid - 1)
迭代与递归的时空复杂度对比

两种实现的时间复杂度均为 O(log n)。但在空间复杂度上,循环迭代版仅占用 O(1) 常数辅助空间;而递归版本每一次函数调用都会压入系统调用栈,空间开销为 O(log n)。在工程中,优先推荐迭代写法以避免递归栈开销。

四、必背变体二:包含重复元素的边界查找

当有序数组中存在重复元素时(例如 nums = [1, 3, 3, 3, 5, 8],寻找 3),基础二分查找只要命中任意一个 3 就会直接返回(可能返回索引 1、2 或 3),无法确保获取首个或最后一个位置。

要解决这个问题,必须在 nums[mid] == target 时不立即返回,而是根据需求继续压迫搜索边界:

1. 寻找最左侧边界(首次出现的位置)

当命中目标时,说明左侧可能还有相同的元素,因此收缩右边界 right = mid - 1,将搜索范围锁定在当前位置的左侧。

binary_search_left_bound.py Python 3.x
def binary_search_left(nums: list[int], target: int) -> int:
    """
    寻找目标值在有序数组中首次出现的下标,若不存在返回 -1
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # 命中不返回,继续向左侧紧缩右边界
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # 循环退出后,检查 left 是否越界且对应的值是否确实为 target
    if left < len(nums) and nums[left] == target:
        return left
    return -1

2. 寻找最右侧边界(最后一次出现的位置)

当命中目标时,说明右侧可能还有相同的元素,因此推进左边界 left = mid + 1,将搜索范围锁定在当前位置的右侧。

binary_search_right_bound.py Python 3.x
def binary_search_right(nums: list[int], target: int) -> int:
    """
    寻找目标值在有序数组中最后一次出现的下标,若不存在返回 -1
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # 命中不返回,继续向右侧推进左边界
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # 循环退出后,检查 right 是否在合法范围内且值确实为 target
    if right >= 0 and nums[right] == target:
        return right
    return -1
python必背源代码二分查找代码
图 3:重复元素场景下左边界与右边界查找的收缩机制与指针收敛对比

五、生产环境推荐:Python 内置 bisect 模块

在实际工程开发中,除非算法面试指明需要手写,否则应当优先使用 Python 标准库中的 bisect 模块。该模块底层基于 C 语言高度优化,不仅执行性能极高,而且逻辑严谨。

函数名称 作用描述 与手写实现的等价关系
bisect.bisect_left(a, x) 在有序列表 a 中寻找 x 的左侧插入点(即首个 >= x 的位置) 若元素存在,返回值就是首个目标值的下标
bisect.bisect_right(a, x) 在有序列表 a 中寻找 x 的右侧插入点(即首个 > x 的位置) 若元素存在,返回值 - 1 就是最后一个目标值的下标
bisect_demo.py Python 标准库用法
import bisect

def find_target_with_bisect(nums: list[int], target: int) -> int:
    """
    利用 Python 标准库 bisect 快速定位目标元素下标
    """
    idx = bisect.bisect_left(nums, target)
    # bisect_left 返回的是插入位置,需要判断该位置的值是否确实等于 target
    if idx < len(nums) and nums[idx] == target:
        return idx
    return -1

# 示例验证
arr = [1, 3, 3, 3, 5, 8]
print("查找 3 的左边界下标:", bisect.bisect_left(arr, 3))       # 输出: 1
print("查找 3 的右侧插入下标:", bisect.bisect_right(arr, 3))    # 输出: 4 (末位下标是 4 - 1 = 3)
print("查找 4 的插入点下标:", bisect.bisect_left(arr, 4))       # 输出: 4 (4 不存在)
print("工程封装函数检索 3:", find_target_with_bisect(arr, 3))    # 输出: 1
print("工程封装函数检索 7:", find_target_with_bisect(arr, 7))    # 输出: -1

六、高频陷阱与避坑全景总结

编写二分查找时,最常见的问题是出现死循环或边界越界。在编码与排查时,应严格对照以下要点:

四个高频易错点检查清单
  • 序列未事先排序:二分查找对未排序数组会产生不可控的错误结果。如果数据无序且只查询一次,直接线性搜索只需 O(n),不必专门耗费 O(n log n) 进行排序。
  • 死循环陷阱:更新指针时如果写成了 left = mid 或 right = mid,在区间长度为 2 时极易陷入循环永不退出的状态。闭区间写法下必须始终使用 left = mid + 1 和 right = mid - 1。
  • 除法符号误写:Python 中单个斜杠 / 为浮点除法,得到的结果是 float 类型,后续作为下标访问列表会抛出 TypeError: list indices must be integers or slices, not float。必须使用双斜杠整除 //。
  • 越界安全保护:当编写左右边界变体或使用 bisect 时,返回的索引可能等于数组长度(即目标比所有元素都大),必须先判断索引合法性再索引元素。
python必背源代码二分查找代码
图 4:二分查找核心知识与避坑决策全景矩阵(数据特征、复杂度、排查清单与工程选型)
相关专题:

本站声明

本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。

Python 相关产品和应用

全部下载

专题列表