在Python中如何使用函数实现二分查找？

二分查找是一种高效的查找算法，也被称为折半查找。其思想是将查找的区间不断二分，找到目标值。在Python中，可以使用函数实现二分查找，本文将介绍如何使用函数实现二分查找。

1. 实现二分查找

二分查找的核心思想是将查找的区间不断缩小。首先确定查找区间的左右边界，然后计算中间元素的位置mid，判断目标值与中间元素的大小关系，从而确定下一次查找的区间。这个过程可以用循环实现，也可以使用递归实现。

下面是循环实现二分查找的代码：

def binary_search(arr, target):
    low, high = 0, 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

其中，arr是待查找的有序数组，target是要查找的目标值。函数的返回值是目标值在数组中的索引，如果没有找到则返回-1。在循环中，我们首先确定区间的左右边界，然后计算中间元素的位置mid，判断目标值与中间元素的大小关系。如果目标值等于中间元素，说明已经找到了，直接返回mid的值。如果目标值比中间元素大，说明目标值可能在右半部分，将区间的左边界移动到mid+1处。如果目标值比中间元素小，则说明目标值可能在左半部分，将区间的右边界移动到mid-1处。如果循环结束后还没有找到目标值，则说明目标值不存在于数组中，返回-1即可。

下面是递归实现二分查找的代码：

def binary_search(arr, target):
    return binary_search_helper(arr, target, 0, len(arr) - 1)
    
def binary_search_helper(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_helper(arr, target, mid + 1, high)
    else:
        return binary_search_helper(arr, target, low, mid - 1)

在递归实现中，我们定义了一个辅助函数binary_search_helper来实现递归过程。函数的参数与循环实现的变量意义相同。首先判断递归退出的条件，即low > high，这是区间已经不可分割的情况，说明目标值不存在于数组中，返回-1即可。否则，在计算中间元素mid的位置后，判断目标值与中间元素的大小关系，然后再递归调用binary_search_helper函数来查找目标值。如果目标值比中间元素大，则在数组的右半部分查找；如果目标值比中间元素小，则在数组的左半部分查找。如果找到目标值，则返回mid的值。

2. 测试二分查找函数

为了测试上述的二分查找函数，我们需要编写一些测试用例，来验证函数的正确性。下面是几个测试用例：

arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr2 = [3, 5, 7, 9, 11]
arr3 = []
target1 = 5
target2 = 3
target3 = 8
target4 = 1
target5 = 0

print(binary_search(arr1, target1)) # 4
print(binary_search(arr2, target2)) # 0
print(binary_search(arr2, target3)) # -1
print(binary_search(arr3, target4)) # -1
print(binary_search(arr1, target5)) # -1

在上述测试用例中，我们定义了三个数组，arr1, arr2, arr3，并分别针对不同的目标值测试函数的返回值。在执行测试用例时，可以通过比较实际的返回值和期望的返回值，来验证函数的正确性。如果函数的返回值和期望值一致，则说明函数实现正确。

3. 总结

在Python中，使用函数实现二分查找算法是比较简单的。我们可以设计一个循环或递归的算法，把区间不断缩小，最终找到目标值。在使用二分查找时，需要注意要求数组是有序的，并且二分查找算法只适用于静态数组，无法处理动态数组。二分查找时间复杂度为O(logn)，是一种非常高效的查找算法。