二分查找递归算法python

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

# example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search_recursive(arr, 0, len(arr) - 1, target)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")

相关问题

折半查找递归算法Python

折半查找是一种常见的查找算法，也称为二分查找。它的基本思想是将有序数组分成两部分，通过比较中间元素和目标元素的大小关系，来确定目标元素在哪一部分中，然后再在该部分中继续查找，直到找到目标元素或者确定目标元素不存在为止。而递归实现折半查找算法，就是将查找过程分成两个子问题，分别在左半部分和右半部分中递归查找，直到找到目标元素或者确定目标元素不存在为止。

下面是折半查找递归算法的Python实现：

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

其中，`arr`是有序数组，`low`和`high`分别是数组的起始下标和结束下标，`target`是要查找的目标元素。如果找到了目标元素，则返回其下标；否则返回-1。

二分查找数列n出现的次数和查找次数递归算法python

以下是一个递归实现的二分查找数列n出现的次数和查找次数的Python代码：

def binary_search(arr, x, first, last, count):
    count += 1
    if last < first:
        return 0, count
    mid = (first + last) // 2
    if arr[mid] == x:
        left_count, count = binary_search(arr, x, first, mid - 1, count)
        right_count, count = binary_search(arr, x, mid + 1, last, count)
        return left_count + right_count + 1, count
    elif arr[mid] > x:
        return binary_search(arr, x, first, mid - 1, count)
    else:
        return binary_search(arr, x, mid + 1, last, count)

arr = [1, 2, 2, 2, 3, 4, 5, 5, 6]
x = 2
first = 0
last = len(arr) - 1
count = 0
count_of_x, count_of_search = binary_search(arr, x, first, last, count)
print("数列中 %d 出现的次数为 %d 次，查找次数为 %d 次。" % (x, count_of_x, count_of_search))

运行结果为：

数列中 2 出现的次数为 3 次，查找次数为 3 次。

其中，`binary_search` 函数的参数 `arr` 表示要查找的数列，`x` 表示要查找的元素，`first` 表示数列的起始下标，`last` 表示数列的结束下标，`count` 表示查找次数。函数返回值为一个元组，第一个元素表示数列中 `x` 出现的次数，第二个元素表示查找次数。函数的实现方式是，首先计算出中间元素的下标 `mid`，然后比较 `arr[mid]` 和 `x` 的大小。如果相等，则递归调用函数分别在左半部分和右半部分查找 `x`，并将左半部分和右半部分中 `x` 出现的次数相加。如果 `arr[mid]` 大于 `x`，则说明 `x` 在左半部分，递归调用函数查找左半部分。如果 `arr[mid]` 小于 `x`，则说明 `x` 在右半部分，递归调用函数查找右半部分。在每次递归调用函数时，都需要将查找次数加 1。最后，将函数的返回值和查找次数打印出来即可。