分治法求数组最大最小值C语言代码n>2时输出错误求解

问题诱因 #

你遇到的问题主要由4个逻辑错误共同导致：

• mid值计算错误：C语言中除法优先级高于加法，原代码mid=low+high/2等价于mid = low + (high / 2)，无法正确取到当前处理区间的中间位置，导致区间拆分逻辑完全错乱。
• 核心问题：缺少分治合并步骤：递归计算完左右两个子区间的最大最小值后，没有将子区间的结果和全局的最大最小值做对比更新，每次处理子区间时会直接覆盖全局存储结果的arrr数组，最终只会保留最左侧长度为2的子区间的计算结果，也就是你观察到的始终输出前两个元素的最大最小值。
• 边界条件判断错误：原代码判断n==1的逻辑针对的是全局数组长度，而非当前递归的子区间长度，当拆分到子区间仅含1个元素的场景时，该判断不会触发，会引发逻辑异常。
• 全局变量更新逻辑不合理：所有子区间的计算结果直接覆盖全局存储的min、max和arrr，没有保留子区间的独立计算结果，无法完成跨子区间的结果对比。

修复方案 #

1. 修正mid计算逻辑为mid = (low + high) / 2，保证正确拆分当前处理的子区间
2. 新增合并逻辑：每次递归计算完左右子区间的结果后，将子区间的最大最小值与全局的最大最小值做对比，更新全局值
3. 修正边界判断：将全局n的判断改为当前子区间长度判断，当low == high时直接更新全局最大最小值
4. 调整全局变量更新时机：递归全流程仅更新min和max两个全局变量，递归全部结束后再统一赋值给arrr输出

修复后完整代码 #

#include<stdio.h>
static int min, max, arrr[100], n;

void minmax(int arr[], int low, int high) {
    int mid;
    // 子区间仅含1个元素
    if (low == high) {
        if (arr[low] < min) min = arr[low];
        if (arr[low] > max) max = arr[low];
        return;
    }
    // 子区间含2个元素
    if (high - low == 1) {
        if (arr[low] < arr[high]) {
            min = arr[low] < min ? arr[low] : min;
            max = arr[high] > max ? arr[high] : max;
        } else {
            min = arr[high] < min ? arr[high] : min;
            max = arr[low] > max ? arr[low] : max;
        }
        return;
    }
    // 正确计算区间中点
    mid = (low + high) / 2;
    // 递归处理左右子区间
    minmax(arr, low, mid);
    minmax(arr, mid + 1, high);
}

int main() {
    int i, low, high;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++) {
        printf("Enter the element %d: ", i);
        scanf("%d", &arr[i]);
    }
    // 初始化全局最大最小值
    min = max = arr[0];
    low = 0;
    high = n - 1;
    minmax(arr, low, high);
    arrr[0] = min;
    arrr[1] = max;
    printf("\nMinimum element %d \nMaximum element %d ", arrr[0], arrr[1]);
    return 0;
}

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