9、 折半查找递归实现（选做） 输入： 第二行： n个元素的值 第三行：要查找的元素x 输出： x元素的位置 实例1： 输入： 1 2 3 4 5 3 输出： 所要查找的元素3的下标为2 实例2： 输入： 5 1 2 3 4 5 6 输出： 所要查找的元素6不存在

折半查找也叫二分查找，它是一种在有序数组中搜索特定元素的高效算法。递归实现时，基本思路是将数组不断二分，每次比较中间元素和目标值，如果相等则返回该位置；如果目标值小于中间元素，则在左半部分继续查找；反之，在右半部分查找。递归的过程会一直持续到找到目标值或确定目标值不存在为止。

以下是递归实现折半查找的一个伪代码示例：

def binary_search_recursive(arr, target, low=0, high=None):
    # 如果high未提供，默认取数组长度减一作为高限
    if high is None:
        high = len(arr) - 1
    
    # 递归基本情况：低索引大于等于高索引，说明没有找到目标
    if low > high:
        return "Element not found"
    
    mid = (low + high) // 2  # 计算中间索引
    
    # 比较目标值与中间元素
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # 目标值在右半部分，更新低限为mid+1
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        # 目标值在左半部分，更新高限为mid - 1
        return binary_search_recursive(arr, target, low, mid - 1)

# 使用示例
arr = [1, 2, 3, 4, 5]
target = 3
position = binary_search_recursive(arr, target)
print(f"The position of element {target} is: {position}")