二分查找python

二分查找是一种常用的查找算法，也称为折半查找。它的基本思想是将已排序的数组分成两部分，通过比较中间元素与目标值的大小，确定目标值可能存在的区间，然后再在该区间内继续进行查找，直到找到目标值或确定目标值不存在为止。

在Python中，我们可以通过递归或循环的方式实现二分查找。我们需要明确二分查找的前提条件，即被查找的数组必须是有序的。假设我们要在一个升序排列的数组中查找目标值，下面是一个使用递归实现的二分查找的示例代码：

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 = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

在上述示例代码中，`binary_search_recursive`函数接受四个参数：被查找的数组`arr`、目标值`target`、当前查找区间的左边界`low`和右边界`high`。判断左边界是否大于右边界，如果是，则说明目标值不存在于数组中，返回-1。然后，计算中间元素的索引`mid`，并与目标值进行比较。如果相等，说明找到了目标值，返回该索引；如果中间元素小于目标值，说明目标值在右半部分，递归调用`binary_search_recursive`函数，将左边界更新为`mid + 1`；如果中间元素大于目标值，说明目标值在左半部分，递归调用`binary_search_recursive`函数，将右边界更新为`mid - 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  # 目标值不存在于数组中
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search_iterative(arr, target)

在上述示例代码中，`binary_search_iterative`函数接受两个参数：被查找的数组`arr`和目标值`target`。初始化左边界`low`为0，右边界`high`为数组长度减1。然后，进入循环，判断左边界是否小于等于右边界，如果是，则继续查找。在循环中，计算中间元素的索引`mid`，并与目标值进行比较。如果相等，说明找到了目标值，返回该索引；如果中间元素小于目标值，说明目标值在右半部分，更新左边界为`mid + 1`；如果中间元素大于目标值，说明目标值在左半部分，更新右边界为`mid - 1`。如果循环结束仍未找到目标值，则说明目标值不存在于数组中，返回-1。

需要注意的是，二分查找要求被查找的数组必须是有序的，否则无法得到正确的结果。二分查找的时间复杂度为O(logn)，其中n为数组的长度。这是因为每次查找都将查找区间缩小一半，因此最多需要logn次查找操作才能找到目标值或确定目标值不存在。