二分查找递归和非递归C语言

### 二分查找算法在C语言中的递归实现与非递归实现

#### 递归实现的特点及代码示例

递归版本的二分查找通过函数调用来不断缩小搜索范围，直到找到目标元素或确认不存在该元素。这种方式直观易懂，但可能存在性能开销。

#include <stdio.h>

// 定义递归版二分查找函数
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        // 如果找到了目标值则返回索引位置
        if (arr[mid] == target)
            return mid;
        
        // 若目标小于中间值，在左子数组继续寻找
        if (arr[mid] > target)
            return binarySearchRecursive(arr, left, mid - 1, target);
            
        // 否则向右子数组查找
        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    // 当未发现匹配项时返回-1表示失败
    return -1;
}

此方法每次都将问题规模减半，理论上效率较高[^1]。

#### 非递归实现的优点及其具体实现方式

相比之下，迭代式的非递归方案利用循环结构来代替多次函数调用，从而避免了潜在的栈溢出风险并减少了不必要的内存消耗。

#include <stdio.h>

// 实现非递归形式的二分查找
int binarySearchIterative(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // 找到目标即刻退出
        if (arr[mid] == target)
            return mid;

        // 调整边界条件准备下一轮判断
        if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    
    // 查找结束仍未定位成功说明数据不在列表内
    return -1;
}

这种方法不仅提高了程序运行的安全性和稳定性，还可能带来更好的执行速度表现[^3]。

#### 性能考量与其他注意事项

尽管两种方法都能有效地完成相同的工作，但在实际应用中更倾向于采用非递归的形式处理大规模数据集或是嵌入式环境中资源受限的情况。此外，对于某些特定场景下的优化需求而言，非递归版本也更容易进行针对性调整和改进[^2]。