二分查找递归实现的内存安全与效率问题咨询

问题背景 #

网上常见的递归二分查找实现如下：

int binsearch(int arr[], int l, int h, int key) {
    if (l < h) {
        int mid = (l + h) / 2;
        if (key == arr[mid])
            return mid;
        else if (key < arr[mid])
            return binsearch(arr, l, mid - 1, key);
        else
            return binsearch(arr, mid + 1, h, key);
    } else {
        return -1; /* 未找到元素时返回-1 */
    }
}

/* 主函数中调用并打印结果 */
printf("%d\n", binsearch(array, 0, n - 1, my_key));

运行这段代码时，无法匹配数组边缘元素（即arr[0]和arr[n-1]），会返回-1。修改后的实现如下：

#include <stdio.h>

int A[] = { -6, -5, -3, -1, 0, 4, 5, 9, 12, 13 }; /* 数组长度n=10 */
int k;

int binsearch(int s, int e, int n) {
    if (s < e) {
        int mid = (s + e) / 2;
        if (n == A[mid]) {
            return mid;
        } else if (n < A[mid]) {
            return binsearch(s, mid, n); /* 修改：原代码是mid-1 */
        } else {
            return binsearch(mid, e, n); /* 修改：原代码是mid+1 */
        }
    } else {
        return -1;
    }
}

int main() {
     printf("key: ");
     scanf("%d", &k);
     printf("Place in array: %d\n", binsearch(0, 10, k)); /* 修改：原代码传n-1即9 */
}

疑问：这些修改是否存在内存安全问题（比如是否会访问数组外内存，原应传9而非10）或效率问题？是否有无需此类修改的解决办法？

问题分析与解答 #

1. 修改后的代码的内存安全风险 #

你的修改确实存在数组越界风险：

• 数组A的有效索引范围是0~9，但调用binsearch时传入的e是10。虽然当前逻辑中mid的计算不会直接到10，但如果后续逻辑调整出现失误，就可能出现访问A[10]的情况，触发未定义行为（比如程序崩溃、数据篡改）。

2. 修改后的代码的效率问题 #

修改后的代码存在无限递归风险，会直接影响程序运行效率甚至导致崩溃：

• 当查找的元素不存在时（比如查找14），递归会进入else分支，调用binsearch(mid, e, n)。假设当前s=9、e=10，mid=(9+10)/2=9，下一次递归还是s=9、e=10，陷入死循环，直到栈溢出。
• 即使元素存在，也可能因为递归次数增加降低效率——原代码每次递归都会将区间缩小至少1，修改后的代码可能重复处理相同区间，增加递归深度。

3. 原代码的正确修复方法 #

原代码的问题在于终止条件错误：当l == h时直接返回-1，但此时arr[l]（即arr[h]）还未被检查，导致边缘元素无法匹配。只需要调整终止条件和逻辑即可，无需修改区间传递方式：

int binsearch(int arr[], int l, int h, int key) {
    // 区间有效时继续查找，包含l==h的情况
    if (l <= h) {
        int mid = l + (h - l) / 2; // 避免l+h溢出，比(l+h)/2更安全
        if (key == arr[mid])
            return mid;
        else if (key < arr[mid])
            return binsearch(arr, l, mid - 1, key);
        else
            return binsearch(arr, mid + 1, h, key);
    } else {
        return -1; // 区间无效，元素不存在
    }
}

调用方式保持不变：binsearch(array, 0, n - 1, my_key)。

这个修复的核心是：

• 将终止条件从l < h改为l <= h，确保区间只剩一个元素时，依然会检查该元素是否等于目标值。
• 使用l + (h - l)/2计算mid，避免当l和h都是较大整数时，l+h溢出的问题。

内容的提问来源于stack exchange，提问作者xcell