试写出折半查找的递归算法

折半查找的递归算法：1. 设定一个搜索范围，通常从数组的最小元素到最大元素。2. 如果范围内只有一个元素，检查该元素，如果它是要查找的元素，则搜索结束，否则搜索失败。3. 如果范围内有多个元素，计算出中间元素，如果该元素是要查找的元素，则搜索结束，否则继续搜索。4. 如果要查找的元素小于中间元素，则将搜索范围缩小到中间元素的左边，重复步骤2和3。5. 如果要查找的元素大于中间元素，则将搜索范围缩小到中间元素的右边，重复步骤2和3。

相关问题

试写出折半查找的递归算法。

折半查找（二分查找）是一种非常高效的查找算法，但是它的递归实现相对来说比较复杂。以下是折半查找的递归算法：

def binary_search(arr, left, right, target):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, mid + 1, right, target)
    else:
        return binary_search(arr, left, mid - 1, target)

以上代码中，`arr`是一个有序数组，`left`和`right`分别是数组的左右边界，`target`是要查找的目标元素。首先判断左右边界是否交叉，如果是则说明没有找到目标元素，返回-1。否则计算中间位置`mid`，如果中间位置的元素等于目标元素，则返回中间位置。如果中间位置的元素小于目标元素，则在右半部分继续查找。如果中间位置的元素大于目标元素，则在左半部分继续查找。这样就可以递归查找目标元素，直到找到为止。

2.请写出折半查找的递归算法，并分析时间性能。

折半查找的递归版本通常会更简洁一些，不过由于循环版本更容易理解并且在效率上没有明显差异，这里仅提供一个递归形式作为参考：

def binary_search_recursive(arr, target, low=0, high=None):
    # 如果高索引小于低索引，表示未找到目标，返回-1
    if high is None or high < low:
        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]
target = 5
result = binary_search_recursive(arr, target)

递归版本的时间性能分析：
- 时间复杂度：二分查找无论递归还是非递归都是O(log n)，其中n是数组长度。每次比较都能将搜索空间减半，直到找到目标或搜索范围为空。
- 空间复杂度：递归版本额外需要存储函数调用栈，对于最坏情况（查找不存在的目标），深度为log n，所以空间复杂度是O(log n)。