折半查找法的递归算法

折半查找法，也称为二分查找法，是一种在有序数组中查找指定元素的算法。下面是折半查找法的递归算法：

1. 首先，确定数组的左边界和右边界。初始时，左边界为0，右边界为数组长度减1。
2. 计算中间元素的索引，即将左边界和右边界相加后除以2，得到中间索引值。
3. 比较中间元素与目标元素的大小：
- 如果中间元素等于目标元素，则返回中间索引值，表示找到了目标元素。
- 如果中间元素大于目标元素，则在左半部分继续查找。将右边界更新为中间索引值减1，然后递归调用折半查找函数。
- 如果中间元素小于目标元素，则在右半部分继续查找。将左边界更新为中间索引值加1，然后递归调用折半查找函数。
4. 重复步骤2和步骤3，直到找到目标元素或者左边界大于右边界为止。

注意：折半查找法要求数组必须是有序的，否则无法保证查找结果的准确性。

相关问题

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

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

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。否则，我们根据中间位置的值和目标值的大小关系分别递归查找左半部分和右半部分。