请实现折半查找的递归算法

好的，折半查找也被称为二分查找，是一种高效的查找算法。

它的基本思想是：将有序数组分成两半，在目标值可能存在的那一半继续查找，直到找到目标值或者确定目标值不存在为止。

以下是折半查找的递归算法：

def binary_search(arr, target, low, high):
    if low > high:
        return -1 # 目标值不存在
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid # 找到目标值
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1) # 在左半部分查找
    else:
        return binary_search(arr, target, mid + 1, high) # 在右半部分查找

其中，arr 表示有序数组，target 表示要查找的目标值，low 和 high 表示当前查找范围的下标范围。

可以先调用这个函数来进行测试：

arr = [1, 3, 5, 7, 9]
target = 3
result = binary_search(arr, target, 0, len(arr) - 1)
print(result) # 1

这里的目标值是 3，在数组中的下标为 1。

相关问题

c语言中实现折半查找递归算法并调用

好的，下面是 C 语言中实现折半查找递归算法的示例代码：

#include <stdio.h>

int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int index = binarySearchRecursive(arr, 0, n - 1, target);
    if (index != -1) {
        printf("找到了，索引为 %d\n", index);
    } else {
        printf("没找到\n");
    }
    return 0;
}

以上代码实现了一个折半查找的递归算法，使用了递归的方式进行查找，时间复杂度为 O(log n)。在主函数中调用了 binarySearchRecursive 函数，并输出查找结果。注意要先定义好数组和目标值，然后传入函数中调用。

折半查找递归算法

折半查找（Binary Search）也称为二分查找，是一种在有序数组中查找目标值的算法。它的基本思想是：在有序数组中，先找到中间位置的元素，将目标值与中间元素进行比较，如果目标值比中间元素小，则在左半部分继续查找；如果目标值比中间元素大，则在右半部分继续查找；如果目标值等于中间元素，则查找成功。

下面是折半查找的递归算法实现（假设数组已经按照升序排列）：

int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) { // 查找失败
        return -1;
    }
    int mid = low + (high - low) / 2; // 计算中间位置
    if (arr[mid] == target) { // 查找成功
        return mid;
    } else if (arr[mid] > target) { // 在左半部分查找
        return binarySearch(arr, low, mid - 1, target);
    } else { // 在右半部分查找
        return binarySearch(arr, mid + 1, high, target);
    }
}

在这个递归函数中，`arr`是要查找的有序数组，`low`和`high`分别是数组的起始位置和结束位置，`target`是要查找的目标值。如果找到了目标值，就返回它在数组中的下标；如果没有找到，就返回-1表示查找失败。