python二分法查找递归

Python中的二分法查找递归是一种搜索算法，它针对有序数组或列表。其基本思想是将待查找区间每次都减半，通过比较中间元素与目标值的关系来逐步缩小范围，直到找到目标值或者确定其不存在于序列中。以下是递归版本的二分查找伪代码：

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low > high:
        return -1  # 目标不在数组内，返回-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)
print(f"Target {target} found at index {result}")

相关问题

python 二分法_二分法查找的递归实现（python）

好的，下面是二分法查找的递归实现（python）：

def binary_search(arr, low, high, x):
 
    # 基本判断
    if high >= low:
 
        mid = (high + low) // 2
 
        # 元素整好的中间位置
        if arr[mid] == x:
            return mid
 
        # 元素小于中间位置的元素，只需要再比较左边的元素
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
 
        # 元素大于中间位置的元素，只需要再比较右边的元素
        else:
            return binary_search(arr, mid + 1, high, x)
 
    else:
        # 不存在
        return -1
 
# 测试数组
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
# 函数调用
result = binary_search(arr, 0, len(arr)-1, x)
 
if result != -1:
    print("元素在数组中的索引为", str(result))
else:
    print("元素不在数组中")

在这个函数中，我们首先判断数组是否为空。如果不为空，我们找到数组的中间元素。如果中间元素与要查找的元素相等，我们就返回中间元素的索引。如果中间元素大于要查找的元素，我们就递归地查找左半部分的元素。如果中间元素小于要查找的元素，我们就递归地查找右半部分的元素。如果要查找的元素不存在于数组中，我们就返回 -1。

希望这能够帮到你！

python递归法实现二分法查找

下面是 Python 代码实现：

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1

其中，`arr` 是要进行查找的有序数组，`low` 和 `high` 为数组的起始和结束索引，`x` 是要查找的数。

如果 `high >= low`，则中间元素 `mid` 取值为 `(high + low) // 2`，即 `mid` 为数组中间的索引。此时，如果 `arr[mid] == x`，则返回 `mid`。如果 `arr[mid] > x`，则说明要查找的数在数组的左半边，递归调用 `binary_search(arr, low, mid - 1, x)`。如果 `arr[mid] < x`，则说明要查找的数在数组的右半边，递归调用 `binary_search(arr, mid + 1, high, x)`。

如果 `high < low`，则说明要查找的数不在数组中，返回 `-1`。

下面是一个使用示例：

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr) - 1, x)

if result != -1:
    print("元素在数组中的索引为", result)
else:
    print("元素不在数组中")

输出结果为：

元素在数组中的索引为 3