未排序数组同时查找最小与最大值的高效算法及方案咨询

现有实现问题反馈 #

• 首先你写的代码有逻辑bug：你定义的left和right是长度为2的数组，分别存对应子区间的最小值和最大值，但后续你用left[n]、left[mid]这种索引去取值是完全错的，直接会报数组越界，正确应该取left[0]当左区间最小值，left[1]当左区间最大值，右区间同理。
• 时间复杂度纠正：你这个算法的时间复杂度是O(n)，你说的O(n/2)其实是常数系数层面的比较次数优化，大O复杂度统计是忽略常数项的。你这个分治思路的最坏比较次数大概是1.5n次，比普通逐个遍历每个元素分别和当前最大最小比的方案（最坏2n次比较）确实要高效。
• 其他小问题：递归实现会占用*O(logn)*的栈空间，数组长度特别大的时候容易栈溢出，而且你直接修改了输入的原数组，属于有副作用的操作，不符合通用函数的设计规范。

更优实现方案 #

其实同时找最大最小值的理论最优最坏比较次数就是ceil(3n/2 - 2)，没有比这个复杂度更低的方案了。你可以用迭代成对比较的方案，和你分治思路的比较次数完全一致，还能避免递归的栈空间开销，参考实现如下：

public static int[] findMinMax(int[] array) {
    int n = array.length;
    if (n == 1) {
        return new int[]{array[0], array[0]};
    }
    int globalMin, globalMax;
    // 初始化全局最大最小值
    if (array[0] > array[1]) {
        globalMin = array[1];
        globalMax = array[0];
    } else {
        globalMin = array[0];
        globalMax = array[1];
    }
    // 步长为2成对遍历
    for (int i = 2; i < n; i += 2) {
        // 数组长度为奇数，最后剩一个单独元素
        if (i == n - 1) {
            globalMin = Math.min(globalMin, array[i]);
            globalMax = Math.max(globalMax, array[i]);
            break;
        }
        int currMin, currMax;
        // 先比较当前两个元素
        if (array[i] < array[i + 1]) {
            currMin = array[i];
            currMax = array[i + 1];
        } else {
            currMin = array[i + 1];
            currMax = array[i];
        }
        // 再和全局值比较
        globalMin = Math.min(globalMin, currMin);
        globalMax = Math.max(globalMax, currMax);
    }
    return new int[]{globalMin, globalMax};
}

这个实现只需要O(1)的额外空间，也不会修改原输入数组，性能更稳定。

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