Python 二分查找算法

以对数 O(log n) 时间搜索排序列表。在 Python 中运行并理解二分搜索，包括分步逻辑、边缘情况和优化。

在编辑器中尝试

概述

二分搜索是一种在排序列表中查找项目的非常有效的算法。与在 O(n) 时间内顺序扫描每个元素的线性搜索不同，二分搜索的工作原理是重复将搜索间隔一分为二。

搜索首先检查数组的中间元素。如果目标值与中间元素匹配，则返回其位置。如果目标较小，算法将搜索范围缩小到下半部分；如果目标较大，则会将其缩小到上半部分。重复此过程，直到找到元素或子数组大小降至零。

为了在 Python 中实现二分搜索，我们使用两个指针（低和高）来跟踪活动搜索边界。由于每一步搜索空间都会减少一半，因此该算法的执行时间为 O(log n)，非常适合海量数据库。

代码和执行输出

标准迭代二分搜索实现，返回排序列表中目标元素的索引。

binary_search.py

在编辑器中尝试

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

端子输出

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

逐步实施

在数据库表中查询索引和搜索
查找连续数学范围内的阈值或边界值
文本字段中的自动完成和搜索功能

常见问题解答

是否必须对列表进行排序才能进行二分搜索？

是的，二分查找严格依赖于被排序的元素。如果列表未排序，比较逻辑就会中断，您必须先对列表进行排序或使用线性搜索。

为什么使用迭代二分搜索而不是递归二分搜索？

虽然递归二分搜索很优雅，但迭代二分搜索在生产中通常是首选。迭代方法在 O(1) 辅助空间中运行，而递归搜索由于调用堆栈而需要 O(log n) 空间，因此在极大的输入上存在堆栈溢出的风险。