如何在 Python 中实现二分查找？

  • mingtian66

    2024-11-10 12:54:48
  • Python
  • 原创

在 Python 中，可以通过递归或迭代的方式来实现二分查找。二分查找的前提是数组必须是有序的，它通过不断将查找范围缩小一半，来快速找到目标值的索引。
1. 递归实现

def binary_search_recursive(arr, target, left, right):
    # 基础情况：如果左指针超过右指针，表示未找到目标值
    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)

使用示例：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(result)  # 输出：4（目标值5的索引）

2. 迭代实现

def binary_search_iterative(arr, target):
    left, right = 0, 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

使用示例：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search_iterative(arr, target)
print(result)  # 输出：4（目标值5的索引）

请使用浏览器的分享功能分享到微信等