Python函数中如何实现二分查找算法？

二分查找算法也被称为折半查找算法，是一种高效的查找方式。它的核心思想是将有序数组分成两部分，确定目标值可能存在的部分，再在该部分继续查找，不断缩小查找范围，最终得到目标值的位置（索引）。这种算法的时间复杂度为 O(logn)，比顺序查找的 O(n) 要快很多。

在Python中实现二分查找算法其实非常简单，可以通过递归或循环两种方式实现，下面分别介绍。

递归实现二分查找算法

递归实现二分查找算法比较容易理解，我们可以将要查找的序列分为两半，如果中间值等于要查找的值就返回该位置，如果中间值比要查找的值大则在左半边查找，否则在右半边查找，重复这个过程直到找到要查找的值或者序列为空。

下面是递归实现的代码实例：

def binary_search_recursive(arr, search_value, start_index, end_index):
    # 如果起始位置大于结束位置，则未找到目标值
    if start_index > end_index:
        return -1
    
    middle_index = (start_index + end_index) // 2
    if arr[middle_index] == search_value:
        # 如果中间值等于要查找的值，则返回中间位置
        return middle_index
    elif arr[middle_index] > search_value:
        # 如果中间值大于要查找的值，则在左半边查找
        return binary_search_recursive(arr, search_value, start_index, middle_index - 1)
    else:
        # 如果中间值小于要查找的值，则在右半边查找
        return binary_search_recursive(arr, search_value, middle_index + 1, end_index)

调用方法如下：

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
search_value = 5
result = binary_search_recursive(arr, search_value, 0, len(arr)-1)
print(result)

输出结果为: 2

循环实现二分查找算法

循环实现二分查找算法也十分简单，我们同样需要将序列分成两半，不过这个过程使用循环完成，每次确定新的起始位置和结束位置，重复这个过程直到找到要查找的值或者序列为空。

下面是循环实现的代码实例：

def binary_search_loop(arr, search_value):
    start_index, end_index = 0, len(arr) - 1
    while start_index <= end_index:
        middle_index = (start_index + end_index) // 2
        if arr[middle_index] == search_value:
            # 如果中间值等于要查找的值，则返回中间位置
            return middle_index
        elif arr[middle_index] > search_value:
            # 如果中间值大于要查找的值，则在左半边查找
            end_index = middle_index - 1
        else:
            # 如果中间值小于要查找的值，则在右半边查找
            start_index = middle_index + 1
    return -1

调用方法如下：

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
search_value = 5
result = binary_search_loop(arr, search_value)
print(result)

输出结果为: 2

总结

二分查找算法是一种高效的查找算法，在处理大数据量查找时明显优于顺序查找。在Python中实现二分查找算法其实非常简单，可以使用递归或循环两种方式实现。无论是哪种方式，我们都需要将要查找的序列不断缩小，直到找到目标值或者序列为空。对于二分查找算法来说，序列必须是有序的。