高效查找的秘密武器：Python二分搜索算法详解（从零开始掌握二分查找）

与逐个遍历的线性搜索相比，高效搜索算法如二分搜索的时间复杂度仅为 O(log n)，这意味着即使面对百万级数据，也能在几十次比较内找到答案！

使用二分搜索的前提条件

• 数据必须是有序的（升序或降序）
• 支持通过索引随机访问（如列表、数组）

Python实现二分搜索

下面我们用两种方式实现二分搜索：迭代法和递归法。

方法一：迭代实现（推荐）

def binary_search(arr, target):    """    在有序列表 arr 中查找 target    返回目标值的索引，若未找到则返回 -1    """    left = 0    right = len(arr) - 1        while left <= right:        mid = (left + right) // 2  # 取中间索引                if arr[mid] == target:            return mid  # 找到目标，返回索引        elif arr[mid] < target:            left = mid + 1  # 目标在右半部分        else:            right = mid - 1  # 目标在左半部分        return -1  # 未找到目标

方法二：递归实现

def binary_search_recursive(arr, target, left=0, right=None):    if right is None:        right = len(arr) - 1        if left > right:        return -1  # 搜索范围无效，未找到        mid = (left + right) // 2        if arr[mid] == target:        return mid    elif arr[mid] < target:        return binary_search_recursive(arr, target, mid + 1, right)    else:        return binary_search_recursive(arr, target, left, mid - 1)

使用示例

# 测试数据（必须是有序的！）numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]# 查找目标值result = binary_search(numbers, 7)if result != -1:    print(f"找到了！7 的索引是 {result}")else:    print("未找到目标值")# 输出：找到了！7 的索引是 3

为什么学习二分搜索？

作为一项基础但强大的技能，Python算法教程中几乎都会涵盖二分搜索。它不仅出现在面试题中，还广泛应用于数据库索引、文件系统、游戏开发等领域。掌握它，你就掌握了处理大规模有序数据的钥匙！

小贴士

• 确保输入数组是有序的，否则结果不可靠
• 注意边界条件，比如空数组、单元素数组
• Python 标准库中的 bisect 模块也提供了二分搜索功能

现在你已经掌握了 Python二分搜索 的核心原理和实现方式！快去试试吧，让查找效率飞起来！