如何在Python中实现binary search算法？含原理、代码与优化建议

1. 二分查找的工作原理 #

二分查找是专门针对有序列表的高效搜索算法，核心逻辑是通过不断缩小搜索范围来快速定位目标元素。它不像线性查找那样逐个遍历元素，而是每次把搜索范围砍掉一半，因此时间复杂度为O(log n)，在数据量较大时，效率远高于线性查找的O(n)。

注意：二分查找的前提是列表必须已经排序，只有这样才能通过中间元素与目标值的大小比较，确定目标元素在左半部分还是右半部分。

2. 算法执行流程分步解析 #

以升序排列的列表为例，二分查找的执行步骤如下：

• 初始化两个指针：low指向列表第一个元素的索引（通常为0），high指向最后一个元素的索引（即len(列表)-1）
• 进入循环：只要low <= high，说明当前搜索范围内还有元素待检查
• 计算中间位置：用整数除法得到中间索引mid = low + (high - low) // 2（这个写法比(low + high) // 2更安全，避免部分语言中整数溢出问题）
• 比较中间元素与目标值：
  • 如果中间元素等于目标值：找到目标，返回mid索引
  • 如果中间元素大于目标值：说明目标在左半部分，将high更新为mid - 1
  • 如果中间元素小于目标值：说明目标在右半部分，将low更新为mid + 1
• 循环结束仍未找到：返回-1（或自定义标记）表示目标元素不存在

3. Python代码示例 #

迭代实现（推荐，避免递归深度限制） #

def binary_search_iterative(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = low + (high - low) // 2
        mid_value = sorted_list[mid]
        
        if mid_value == target:
            return mid  # 返回找到的元素索引
        elif mid_value > target:
            high = mid - 1  # 目标在左半部分，缩小右边界
        else:
            low = mid + 1  # 目标在右半部分，扩大左边界
    return -1  # 未找到目标元素

# 测试代码
if __name__ == "__main__":
    sorted_numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    target = 23
    result_index = binary_search_iterative(sorted_numbers, target)
    
    if result_index != -1:
        print(f"元素 {target} 位于索引 {result_index}")
    else:
        print(f"元素 {target} 不在列表中")

递归实现（适合理解递归逻辑，注意递归深度） #

def binary_search_recursive(sorted_list, target, low, high):
    # 递归终止条件：搜索范围为空
    if low > high:
        return -1
    
    mid = low + (high - low) // 2
    mid_value = sorted_list[mid]
    
    if mid_value == target:
        return mid
    elif mid_value > target:
        # 递归搜索左半部分
        return binary_search_recursive(sorted_list, target, low, mid - 1)
    else:
        # 递归搜索右半部分
        return binary_search_recursive(sorted_list, target, mid + 1, high)

# 测试代码
if __name__ == "__main__":
    sorted_numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    target = 56
    result_index = binary_search_recursive(sorted_numbers, target, 0, len(sorted_numbers)-1)
    
    if result_index != -1:
        print(f"元素 {target} 位于索引 {result_index}")
    else:
        print(f"元素 {target} 不在列表中")

4. 使用时需注意的边界情况与事项 #

• 必须依赖有序列表：如果列表未排序，二分查找的结果完全不可靠，甚至会报错
• 空列表处理：传入空列表时，要直接返回不存在标记，避免索引越界错误
• 重复元素问题：如果列表中有多个相同的目标值，二分查找只会返回其中一个的索引（通常是中间位置的那个），若需获取所有重复项，需额外遍历左右相邻元素
• 索引计算安全：虽然Python支持大整数不会溢出，但其他语言中(low + high)可能超出整数范围，因此推荐用low + (high - low) // 2计算中间索引
• 目标值超出列表范围：当目标值小于列表最小值或大于最大值时，循环会正常结束并返回不存在标记，无需额外处理，但要确保代码能正确识别这种情况

5. 优化建议与替代方案 #

优化方向 #

• 插值查找：如果列表元素分布均匀（如等差数列），可以用插值查找替代二分查找。它通过估算目标值的位置来缩小搜索范围，平均时间复杂度优于O(log n)，但最坏情况仍为O(n)
• 斐波那契查找：利用斐波那契数列确定中间位置，减少除法运算，适合硬件除法效率较低的场景

替代方案 #

• 线性查找：适用于数据量极小的场景，实现简单，无需提前排序
• Python标准库bisect模块：Python内置了二分查找的实现，无需自己写代码，比如bisect.bisect_left可以快速找到目标值应插入的位置，从而判断是否存在：

  import bisect
  
  sorted_numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
  target = 23
  insert_pos = bisect.bisect_left(sorted_numbers, target)
  
  if insert_pos < len(sorted_numbers) and sorted_numbers[insert_pos] == target:
      print(f"元素 {target} 位于索引 {insert_pos}")
  else:
      print(f"元素 {target} 不在列表中")
  

• 哈希表查找：如果需要多次执行查找操作，可以将列表转换为集合或字典，查找时间复杂度为O(1)，但会占用额外空间，且无法保留元素的索引信息

内容的提问来源于stack exchange，提问作者Jagan Pradhan