写出二分查找的递归算法

二分查找的递归算法如下：

1. 定义一个函数，传入一个有序数组、查找的元素、数组的起始位置和结束位置。

2. 计算数组的中间位置 mid，如果 mid 对应的元素等于查找的元素，则返回 mid。

3. 如果 mid 对应的元素大于查找的元素，则在数组的左半部分继续查找，即递归调用函数，传入数组、查找的元素、起始位置和 mid-1。

4. 如果 mid 对应的元素小于查找的元素，则在数组的右半部分继续查找，即递归调用函数，传入数组、查找的元素、mid+1 和结束位置。

5. 如果起始位置大于结束位置，则说明数组中不存在查找的元素，返回 -1。

6. 完成递归查找后，返回查找到的元素的下标。

代码实现如下：

int binarySearch(int arr[], int x, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binarySearch(arr, x, low, mid - 1);
} else {
return binarySearch(arr, x, mid + 1, high);
}
}

相关问题

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

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

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)。