如何使用分治算法查找数组中第一个不符合n+1递增序列的元素

核心问题根因 #

你当前的实现存在3个关键缺陷：

• 完全遗漏了左右子数组衔接位置的合法性检查：左右两个子数组各自内部符合递增规则，不代表两个子数组衔接的位置（左半最后一个元素和右半第一个元素）也符合规则，这是你示例返回6而非3的核心原因。以你的示例中B段数组[8,9,3,6]为例，左半[8,9]内部无异常，右半[3,6]返回异常值6，你的代码直接返回6，完全没检查到9和3的衔接不符合规则。
• 数组分割逻辑有缺陷：对于奇数长度的数组，你会直接丢弃最后一个元素，且每次手动复制数组不仅效率低，还极易出现边界错误。
• 缺少长度为1的基线条件处理：如果子数组长度为1，你的代码既不匹配listSize<1也不匹配listSize==2，会进入异常逻辑，甚至触发死递归或数组越界。

修复思路 #

1. 改用索引区间的方式实现分治，不需要复制数组，既避免元素丢失，也提升运行效率。
2. 补充左右子数组衔接位置的检查逻辑：左半段无异常时，先检查衔接位置是否符合规则，再检查右半段。
3. 补全基线条件，覆盖所有边界情况。

修复后完整代码 #

// 分治辅助函数，处理[left, right]闭区间的检查
int helper(int list[], int left, int right) {
    // 区间长度小于2，无相邻元素，无异常
    if (right - left + 1 < 2) {
        return -1;
    }
    // 区间长度为2，直接检查相邻元素
    if (right - left + 1 == 2) {
        return list[right] == list[left] + 1 ? -1 : list[right];
    }
    int mid = left + (right - left) / 2;
    // 优先检查左半段，保证返回第一个异常值
    int leftRes = helper(list, left, mid);
    if (leftRes != -1) {
        return leftRes;
    }
    // 检查左右段衔接位置
    if (list[mid + 1] != list[mid] + 1) {
        return list[mid + 1];
    }
    // 最后检查右半段
    return helper(list, mid + 1, right);
}

// 对外暴露的接口，参数和原实现保持兼容
int findFirst_divideandconquer(int list[], int listSize) {
    if (listSize < 2) {
        return -1;
    }
    return helper(list, 0, listSize - 1);
}

验证效果 #

用你给出的示例数组{4, 5, 6, 7, 8, 9, 3, 6, 7}测试，函数会正确返回第一个异常值3，所有元素符合规则的数组会返回-1，奇数/偶数长度的数组都可以正常处理。

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