折半查找递归算法代码

折半查找递归算法在给定有序数组`arr`中查找目标值`target`的过程如下：

def binary_search_recursion(arr, target, low, high):
    """
    递归版本的折半查找
    :param arr: 排序后的整数数组
    :param target: 要查找的目标值
    :param low: 数组下界的索引
    :param high: 数组上界的索引
    :return: 目标值的索引（如果找到），否则返回-1
    """
    if low > high:  # 当搜索范围为空时，表示未找到目标值
        return -1
    
    mid = (low + high) // 2  # 计算中间位置
    if arr[mid] == target:  # 如果找到目标值，直接返回索引
        return mid
    elif arr[mid] < target:  # 如果中间值小于目标，缩小左半部分的搜索范围
        return binary_search_recursion(arr, target, mid + 1, high)
    else:  # 否则，缩小右半部分的搜索范围
        return binary_search_recursion(arr, target, low, mid - 1)

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search_recursion(arr, target, 0, len(arr) - 1)
if result != -1:
    print(f"元素 {target} 的索引是：{result}")
else:
    print(f"{target} 不在数组中")