Recursively find minimum and maximum values in an array

Question

Attaching what I've done; having a problem that the recursion sticks on the left recursive calls and can't continue to the right recursive calls. can't figure out how to return the recursion to the first position and continue the program to run towards the right recursive calls.

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);

}

It seems to me that you are overcomplicating, or i don't understand what you want. So, minMax is working like this: from{3, 5, 17, 4, 2,5} the min should be 2, the max should be 17, not? — Lasoloz
– Lasoloz, Commented Dec 13, 2015 at 11:37
yes, I know there's a simpler solution. though I would like to solve it recursively and using the binary search pattern. — Ami
– Ami, Commented Dec 13, 2015 at 11:39
No, there is a simpler recursive function. I'll write it and if you want, use it. — Lasoloz
– Lasoloz, Commented Dec 13, 2015 at 11:41

DhruvJoshi · Accepted Answer · 2015-12-13 12:31:08Z

Similar approach as the merge sort :

Here is the recursive solution in C : a is your array, i and j your left and right ...

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;
}

}

Although there are a lot of different and easier solutions ...

Edit by Question asker: ...because the question was about C++ program, this would be the C++ version

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;
    }
}

Lasoloz · Accepted Answer · 2015-12-13 11:49:41Z

1

A simpler recursion is:

void minMax(int& A[], int index, const int& lenght, int& min, int& max)
{
if (A[index] < min) min = A[index]);
else if (A[index] > max) max= A [index];

if (++index < lenght) minMax(A, index, lenght, min, max);
}

In this case you just iterate through recursively, and not left-right.

answered Dec 13, 2015 at 11:49

Lasoloz

2623 silver badges11 bronze badges

Collectives™ on Stack Overflow

Recursively find minimum and maximum values in an array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related