c++ - 递归查找数组中的最小值和最大值

Question

附上我所做的；有一个问题，递归停留在左边的递归调用上，不能继续右边的递归调用。无法弄清楚如何将递归返回到第一个位置并继续程序向正确的递归调用运行。

void minMax(int A[], int left, int right, int &min, int &max)
{
    if (right == 0)
        return;
    if (A[(left + right) / 2] <= min)
        min = A[(left + right) / 2];
    if (A[((left + right) / 2)] >= max)
        max = A[((left + right) / 2)];
    if (right > 0)
        minMax(A, left, (right - left) / 2, min, max);
    if(left < right)
        minMax(A, (right - left) / 2, right, min, max);

}

Answer 1

与归并排序类似的方法:

这是 C 中的递归解决方案:a 是你的数组，i 和 j 你的左边和右边......

void minmax (int* a, int i, int j, int* min, int* max) {
int lmin, lmax, rmin, rmax, mid;
if (i == j) {
*min = a[i];
*max = a[j];
} else if (j == i + 1) {
if (a[i] > a[j]) {
  *min = a[j];
  *max = a[i];
} else {
  *min = a[i];
  *max = a[j];
}
} else {
mid = (i + j) / 2;
minmax(a, i, mid, &lmin, &lmax);
minmax(a, mid + 1, j, &rmin, &rmax);
*min = (lmin > rmin) ? rmin : lmin;
*max = (lmax > rmax) ? lmax : rmax;
}

}

虽然有很多不同且更简单的解决方案......

由问题提问者编辑: ...因为问题是关于 C++ 程序的，所以这将是 C++ 版本

void minMax(int a[], int left, int right, int &min, int& max) {
    int lmin, lmax, rmin, rmax, mid;
    if (left == right)
    {
        min = a[left];
        max = a[right];
    }
    else if (right == left + 1)
    {
        if (a[left] > a[right])
        {
            min = a[right];
            max = a[left];
        }
        else
        {
            min = a[left];
            max = a[right];
        }
    }
    else
    {
        mid = (left + right) / 2;
        minMax(a, left, mid, lmin, lmax);
        minMax(a, mid + 1, right, rmin, rmax);

        if (lmin > rmin)
            min = rmin;
        else
            min = lmin;
        if (lmax > rmax)
            max = lmax;
        else
            max = rmax;
    }
}