C语言数据结构中二分查找递归非递归实现并分析

C语言数据结构中二分查找递归及非递归实现

二分查找基本原理

二分查找（Binary Search）是一种基于比较目标值和中间元素的教科书式算法。每次查找都将查找范围缩小一半，直到找到目标值为止，或发现查找范围已经为空。

二分查找前提条件

在使用二分查找之前，我们需要满足以下两个前提条件：

• 数组必须是有序的。
• 数组需要支持随机访问，也就是支持索引。

二分查找的两种方法

在C语言中，我们通常使用两种方式实现二分查找：递归和非递归。

递归方法实现二分查找

递归实现二分查找通常需要定义一个辅助函数，如下所示：

#include <stdio.h>

int binaryRecursiveSearch(int *arr, int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int middle = (low + high) / 2;
    if (arr[middle] == target) {
        return middle;
    }
    if (arr[middle] > target) {
        return binaryRecursiveSearch(arr, low, middle - 1, target);
    } else {
        return binaryRecursiveSearch(arr, middle + 1, high, target);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int length = sizeof(arr) / sizeof(int);
    int target = 11;
    int index = binaryRecursiveSearch(arr, 0, length - 1, target);
    printf("Target %d is located at %d.\n", target, index);
    return 0;
}

在上述代码中，binaryRecursiveSearch 函数是一个递归函数，接收四个参数：

• arr表示要查找的数组；
• low表示数组范围的最小索引；
• high表示数组范围的最大索引；
• target表示要查找的目标元素。

首先，函数会计算出数组范围的中间索引，并将其保存在 middle 变量中。接着，如果 arr[middle] == target，则说明目标元素就是这个中间元素，直接返回 middle。如果 arr[middle] > target，则说明目标元素在数组范围的左半部分，于是递归调用 binaryRecursiveSearch(arr, low, middle - 1, target)；否则，目标元素就在数组范围的右半部分，递归调用 binaryRecursiveSearch(arr, middle + 1, high, target)。如果递归到数组范围为空，即 low > high，则返回 -1 表示未找到目标元素。

我们可以将上述函数调用一个示例，如下所示：

int arr[] = {1, 3, 5, 7, 9, 11, 13};
int length = sizeof(arr) / sizeof(int);
int target = 11;
int index = binaryRecursiveSearch(arr, 0, length - 1, target);
printf("Target %d is located at %d.\n", target, index);

在上述代码中，我们先定义一个有序的数组 arr，然后计算出数组的长度 length 和要查找的目标元素 target。最后，我们调用递归函数 binaryRecursiveSearch(arr, 0, length - 1, target)，找到目标元素在数组中的索引。

非递归方法实现二分查找

非递归方式实现二分查找相较于递归方式略显繁琐，但却可以避免函数调用栈大小不断增长的问题，同时也可以节省时间。

非递归方式实现二分查找示例代码如下：

#include <stdio.h>

int binaryIterativeSearch(int *arr, int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (arr[middle] == target) {
            return middle;
        } else if (arr[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int length = sizeof(arr) / sizeof(int);
    int target = 11;
    int index = binaryIterativeSearch(arr, length, target);
    printf("Target %d is located at %d.\n", target, index);
    return 0;
}

在上述代码中，我们定义了一个名为 binaryIterativeSearch 的函数。与递归方式不同，迭代式查找需要三个参数：

• arr 表示要查找的数组；
• size 表示数组的长度；
• target 表示要查找的目标元素。

函数中，我们首先定义了两个变量 left 和 right，分别用于表示数组的最小索引和最大索引。通过不断缩小范围，最终找到目标元素或返回 -1 表示未找到。具体实现如下：

• 每次找到中间元素 middle = (left + right) / 2。
• 如果 arr[middle] == target，直接返回 middle。
• 如果 arr[middle] > target，说明要查找的元素在数组的左半部分，于是右边界 right 变成了 middle - 1。
• 如果 arr[middle] < target，说明要查找的元素在数组的右半部分，于是左边界 left 变成了 middle + 1。
• 不断缩小范围，直到找到或未找到。

我们可以通过一个示例代码来演示非递归方式实现二分查找：

int arr[] = {1, 3, 5, 7, 9, 11, 13};
int length = sizeof(arr) / sizeof(int);
int target = 11;
int index = binaryIterativeSearch(arr, length, target);
printf("Target %d is located at %d.\n", target, index);

在上述代码中，我们先定义一个有序的数组 arr，然后计算出数组的长度 length 和要查找的目标元素 target。最后，我们调用非递归函数 binaryIterativeSearch(arr, length, target)，找到目标元素在数组中的索引。

总结

本文演示了C语言数据结构中二分查找的递归和非递归两种实现方式，并且讲解了二分查找的基本原理和前提条件，希望对读者掌握二分查找有所帮助。

示例说明

1. 递归实现二分查找

在示例中，定义一个有序的数组 arr，然后计算出数组的长度 length 和要查找的目标元素 target。最后，调用递归函数 binaryRecursiveSearch(arr, 0, length - 1, target)，找到目标元素在数组中的索引。

1. 非递归实现二分查找

在示例中，定义一个有序的数组 arr，然后计算出数组的长度 length 和要查找的目标元素 target。最后，调用非递归函数 binaryIterativeSearch(arr, length, target)，找到目标元素在数组中的索引。