试将折半查找法改写为递归算法。 【问题】源代码或伪代码粘贴在下方,用C语言

以下是折半查找法的递归算法的C语言代码：

int binarySearch(int arr[], int low, int high, int x) {
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, low, mid - 1, x);
        return binarySearch(arr, mid + 1, high, x);
    }
    return -1;
}

其中，arr是待查找的有序数组，low和high是数组的开始和结束位置，x是要查找的元素。如果找到了x，返回x在数组中的下标；否则返回-1。

相关问题

试将折半查找法改写为递归算法

好的，我来为您解答。折半查找法也叫二分查找法，是一种很常用的查找算法。下面是折半查找法的非递归实现：

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

现在我们将其改写为递归算法：

int binarySearchRecursion(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 binarySearchRecursion(arr, left, mid - 1, target);
    else
        return binarySearchRecursion(arr, mid + 1, right, target);
}

可以看到，递归算法的思想与非递归算法相同，只是将循环改成了递归函数调用，同时将循环条件改为递归终止条件。

试将折半查找法改写为递归算法。

好的，折半查找法的非递归实现如下：

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

现在我们来将其改写为递归算法：

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

我们可以看到，在递归算法中，我们首先判断了递归的终止条件，即左指针大于右指针时，返回 -1。然后计算中间位置，如果中间位置的值等于目标值，直接返回 mid。否则，我们根据中间位置的值和目标值的大小关系分别递归查找左半部分和右半部分。