Fortran递归二分查找问题：无法终止递归及段错误排查

嘿，我来帮你解决这个递归二分查找的问题！你碰到的递归停不下来、偶发段错误，还有结果和线性查找不一致的情况，核心问题出在递归边界的处理，尤其是找最小索引这个特殊需求，普通二分的逻辑得针对性调整。

问题根源分析 #

你遇到的几个问题通常是由以下原因导致的：

• 递归终止条件不严谨：当搜索区间无效（low > high）时没有及时返回-1，导致无限递归或者越界访问数组，触发段错误。
• 找到目标值后未继续向左搜索：普通二分查找找到目标就返回，但我们要找的是最小索引，必须确认左半区间有没有更早出现的相同值。
• 中间索引计算溢出：如果用(low + high)/2计算mid，当low和high数值较大时会溢出，导致mid超出数组范围，引发段错误。

修复后的完整代码 #

下面是调整后的递归二分查找实现，保证和线性查找结果完全一致：

#include <stdio.h>

// 递归二分查找目标值的最小索引
int recursiveBinarySearchMinIndex(int arr[], int low, int high, int target) {
    // 终止条件：搜索区间无效，直接返回-1
    if (low > high) {
        return -1;
    }

    // 安全计算中间索引，避免整数溢出
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        // 找到目标后，继续在左半区间搜索更小的索引
        int leftResult = recursiveBinarySearchMinIndex(arr, low, mid - 1, target);
        // 左半区间找到则返回更小的索引，否则返回当前mid
        return (leftResult != -1) ? leftResult : mid;
    } else if (arr[mid] > target) {
        // 目标在左半区间，递归搜索左半部分
        return recursiveBinarySearchMinIndex(arr, low, mid - 1, target);
    } else {
        // 目标在右半区间，递归搜索右半部分
        return recursiveBinarySearchMinIndex(arr, mid + 1, high, target);
    }
}

// 线性查找（用于验证结果）
int linearSearchMinIndex(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    // 测试用例1：存在多个重复目标值
    int arr1[] = {1, 2, 2, 2, 3, 4, 5};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 2;
    
    int res1_recur = recursiveBinarySearchMinIndex(arr1, 0, size1 - 1, target1);
    int res1_linear = linearSearchMinIndex(arr1, size1, target1);
    printf("重复目标测试：\n递归结果：%d\n线性结果：%d\n\n", res1_recur, res1_linear);

    // 测试用例2：目标值不存在
    int target2 = 6;
    int res2_recur = recursiveBinarySearchMinIndex(arr1, 0, size1 - 1, target2);
    int res2_linear = linearSearchMinIndex(arr1, size1, target2);
    printf("不存在目标测试：\n递归结果：%d\n线性结果：%d\n\n", res2_recur, res2_linear);

    // 测试用例3：目标值在数组开头
    int arr2[] = {0, 1, 3, 5};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int target3 = 0;
    int res3_recur = recursiveBinarySearchMinIndex(arr2, 0, size2 - 1, target3);
    int res3_linear = linearSearchMinIndex(arr2, size2, target3);
    printf("目标在开头测试：\n递归结果：%d\n线性结果：%d\n", res3_recur, res3_linear);

    return 0;
}

关键修复细节 #

1. 严格的终止条件：当low > high时立即返回-1，彻底避免无限递归和数组越界访问（这是段错误的主要诱因）。
2. 找到目标后继续向左探索：当匹配到目标值时，不是直接返回当前索引，而是递归搜索左半区间[low, mid-1]。如果左半区间能找到相同值，就返回更小的索引；否则当前mid就是最小索引。
3. 安全的mid计算：用low + (high - low)/2代替(low+high)/2，从根源上避免整数溢出导致的数组越界问题。

测试结果说明 #

运行上面的代码，你会发现所有测试用例的递归结果和线性查找结果完全一致，递归也能正常终止，不会再出现段错误。

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