C#字符串数组多匹配项递归二分查找触发StackOverflowException求解

问题根因排查方向 #

• 递归终止条件错误：这是递归二分栈溢出最常见的原因，检查你是否在左右边界交叉时仍然继续递归，尤其是多匹配项查询场景下，很可能为了找相邻的匹配值，没有正确终止左右分支的递归，导致边界卡死循环递归。
• 边界计算逻辑错误：检查mid的计算是否溢出，以及递归调用时左右边界的赋值是否正确，比如查左半区时是否将右边界设为mid - 1、查右半区时是否将左边界设为mid + 1，如果错误将边界设为mid而不做偏移，当左右边界相邻时会直接陷入无限递归。
• 未加限制的多分支递归逻辑：因为你需要返回多个匹配索引，大概率在匹配到目标值之后同时开启了左半区和右半区的递归搜索，但是没有给这两个子递归加上独立的终止条件，导致两个分支都进入无限递归。
• 有序性校验缺失：二分查找的前置条件是操作预排序的数组，如果数组未排序，会导致比较逻辑完全错乱，递归走错误分支触发边界死循环。

代码修复方案 #

针对多匹配项的递归二分查找，参考修复逻辑如下：

// 多匹配递归二分查找标准实现
List<int> SearchMulti(string[] sortedArr, string target, int left, int right) {
    var result = new List<int>();
    // 递归终止条件必须放在最前面，边界交叉直接返回空
    if (left > right) return result;
    int mid = left + (right - left) / 2; // 避免int溢出的mid计算方式
    if (sortedArr[mid] == target) {
        result.Add(mid);
        // 分别搜索左右半区的相邻匹配项
        result.AddRange(SearchMulti(sortedArr, target, left, mid - 1));
        result.AddRange(SearchMulti(sortedArr, target, mid + 1, right));
    } else if (string.Compare(sortedArr[mid], target) < 0) {
        // 目标值更大，仅搜索右半区
        result.AddRange(SearchMulti(sortedArr, target, mid + 1, right));
    } else {
        // 目标值更小，仅搜索左半区
        result.AddRange(SearchMulti(sortedArr, target, left, mid - 1));
    }
    return result;
}

调用时传入初始边界left=0、right=数组长度-1即可，注意字符串比较要统一大小写规则，避免匹配逻辑错误导致递归走错误分支。

更稳定的替代实现思路 #

你在仅5组测试数据的场景下就触发了栈溢出，说明递归逻辑的缺陷非常明显，建议直接改用迭代方案，完全规避栈溢出风险：

• 数据量少于1000条时直接用遍历查找，代码复杂度最低，几乎不会出现逻辑错误
• 数据量较大时用迭代二分查找先定位到任意一个匹配项，再向左右遍历收集所有相邻的匹配项，效率和递归二分一致且没有栈溢出风险

// 迭代实现多匹配二分查找示例
List<int> SearchMultiIterative(string[] sortedArr, string target) {
    var result = new List<int>();
    int left = 0, right = sortedArr.Length - 1;
    int matchIndex = -1;
    // 第一步：先找任意一个匹配项
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = string.Compare(sortedArr[mid], target);
        if (cmp == 0) {
            matchIndex = mid;
            break;
        } else if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (matchIndex == -1) return result;
    // 第二步：向左收集所有匹配项
    int p = matchIndex;
    while (p >= 0 && sortedArr[p] == target) {
        result.Add(p);
        p--;
    }
    // 第三步：向右收集所有匹配项
    p = matchIndex + 1;
    while (p < sortedArr.Length && sortedArr[p] == target) {
        result.Add(p);
        p++;
    }
    return result;
}

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