在Python中实现二分查找函数

二分查找（Binary Search）是一种查找算法，它通过将待查找的数据元素不断地与数组的中间元素进行比较，从而将查找范围逐渐缩小，直到找到目标元素或确定目标元素不存在为止。二分查找算法的时间复杂度为 O(logn)。

在Python中实现二分查找函数，可以分为迭代实现和递归实现两种方式。

1. 迭代实现二分查找函数

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

上述代码中，使用low和high表示待查找范围的左右边界，通过循环不断将target与中间元素进行比较，并根据比较结果更新左右边界。如果找到了目标元素target，则返回其索引；如果没有找到目标元素，则返回 -1。

2. 递归实现二分查找函数

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

以上代码为递归实现版本，通过递归调用自身来不断缩小查找范围，并最终找到目标元素或确定其不存在。

使用二分查找函数时，需要确保待查找的数组是有序的。如果数组无序，可以先对其进行排序。

下面是一个使用二分查找函数的例子：

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 16

index_iterative = binary_search_iterative(arr, target)
index_recursive = binary_search_recursive(arr, target, 0, len(arr) - 1)

if index_iterative != -1:
    print(f"迭代查找：目标元素 {target} 的索引为：{index_iterative}")
else:
    print(f"迭代查找：目标元素 {target} 不存在")

if index_recursive != -1:
    print(f"递归查找：目标元素 {target} 的索引为：{index_recursive}")
else:
    print(f"递归查找：目标元素 {target} 不存在")

以上代码首先定义了一个有序数组arr，然后调用二分查找函数进行查找，使用两种方式分别实现并打印目标元素的索引或不存在的提示信息。

总结：

本文介绍了在Python中实现二分查找函数的两种方式：迭代实现和递归实现。无论哪种方式，都需要保证待查找的数组是有序的。使用二分查找的时间复杂度为 O(logn)，是一种高效的查找算法。