分别用递归方式和非递归方式实现有序顺序表的二分检索

二分检索是一种常见的算法，在有序序列或有序数组中查找指定元素。

在有序序列或数组中，我们可以通过比较中间元素与指定元素来确定要搜索的部分。如果指定元素小于中间元素，则搜索左半部分；如果指定元素大于中间元素，则搜索右半部分。这个过程重复进行，直到找到指定元素或确认无法找到为止。

非递归算法使用循环实现，而递归算法使用函数调用实现。递归算法实现较简单，但需要额外的空间来存储递归调用的状态，可能导致栈溢出。非递归算法则可以优化空间复杂度，但可能实现较为复杂。

相关问题

用递归方式实现有序顺序表的二分检索 c语音代码

好的，以下是用递归方式实现有序顺序表的二分检索的C语言代码：

int binary_search(int arr[], int left, int right, int target) {
    if (left > right) { // 递归结束条件，未找到目标元素
        return -1;
    }
    int mid = (left + right) / 2;
    if (arr[mid] == target) { // 找到目标元素，返回下标
        return mid;
    } else if (arr[mid] > target) { // 目标元素在左半部分
        return binary_search(arr, left, mid - 1, target); // 递归查找左半部分
    } else { // 目标元素在右半部分
        return binary_search(arr, mid + 1, right, target); // 递归查找右半部分
    }
}

其中，arr为有序顺序表，left和right为有序顺序表的左右边界，target为要查找的目标元素。函数返回目标元素在有序顺序表中的下标，如果未找到，返回-1。

用c语言实现递归方式的有序顺序表的二分检索

下面是用 C 语言实现递归方式的有序顺序表的二分检索的代码：

#include <stdio.h>

#define MAX_SIZE 10

int binarySearch(int arr[], int left, int right, int target);

int main() {
    int arr[] = {1, 3, 4, 6, 8, 9, 11, 12, 15, 19};
    int target = 8;
    int index = binarySearch(arr, 0, MAX_SIZE - 1, target);
    if (index != -1) {
        printf("The target %d is at index %d\n", target, index);
    } else {
        printf("The target %d is not found\n", target);
    }
    return 0;
}

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

在该代码中，我们定义了一个有序顺序表 `arr`，并且我们想要在其中查找一个目标值 `target`。我们使用了递归方式的二分查找算法，该算法的基本思想是不断将有序顺序表的搜索范围缩小一半，直到找到目标值或者确认目标值不存在为止。

首先，我们定义了一个 `binarySearch` 函数来实现递归方式的二分查找。该函数的参数包括有序顺序表 `arr`、搜索范围的左右边界 `left` 和 `right`，以及目标值 `target`。该函数首先检查搜索范围是否为空，如果是，则说明目标值不存在，返回 `-1`。否则，计算中间元素的下标 `mid`，并且将目标值与中间元素进行比较。如果相等，则返回 `mid`。如果目标值比中间元素大，则递归调用 `binarySearch` 函数，在右半部分查找目标值。如果目标值比中间元素小，则递归调用 `binarySearch` 函数，在左半部分查找目标值。

最后，在 `main` 函数中，我们调用了 `binarySearch` 函数来查找目标值 `target` 在有序顺序表 `arr` 中的下标。如果找到了目标值，则输出其下标；否则，输出未找到目标值的消息。