creating a recursive way to find max and min in array

[-EquinoX-]

I am kind of confused with this instruction:

Describe a recursive algorithm for finding both the minimum and maximum elements in an array A of n elements. Your method should return a pair (a,b), where a is the minimum element and b is the maximum.

how is this possible?? can someone describe me the pseudo code of doing this recursively?

[legend986]

I think a slight variant of the binary search can be used to solve this problem. It is O(log n) on a sorted array.

[-EquinoX-]

using binary search in recursion to find the max and min in an array?? I have no idea to do this?

[legend986]

Binary search is depicted here using recursion:

http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html

As I said, you will have to work out how to achieve both the min and max though...

[-EquinoX-]

thanks legend986, I just don't know how a method could return two values though.. can you give me an example of a function that returns 2 function?

One more concern is that, if I manipulate binary search into this method min and max that I want, then the array has to be sorted first right? Therefore the min and max is already known, which is the first and last value in the array. If that's so what's the purpose?? So I guess by looking at this, the array shouldn't be unsorted like the one in binary search is, if it does then what's the purpose of creating this method.

You mentioned that it's kind of similar with binary search, is it the same in the way it divides the array into two first??

I know how to find the max value in an array, which is:


int findMax(int array[], int size, int index)
{
// This needs to be size - 1 because the array is 0-indexed.
// This is our base case
if (index == size - 1) return array[index];

// Call the function recursively on less of the array
int result = findMax(array, size, index + 1);

// Return the max of (the first element we are examining, the max of the
// rest of the array)
if (array[index] > result)
return array[index];
else
return result;
}


but how do I find both the min and max at the same time and returning both at the same time??

[CMPITG]

Use reference variables in C++ or pointers in C:
int findMax(int array[], int size, int index, int &minValue, int &maxValue);
int findMax(int array[], int size, int index, int *minValue, int *maxValue);

[spoon!]

to the OP:
how about this

array_min(array of length 1) = array[0]
otherwise:
array_min(array) = min(array[0], array_min(rest of array))

same for max

[-EquinoX-]

to the OP:
how about this

array_min(array of length 1) = array[0]
otherwise:
array_min(array) = min(array[0], array_min(rest of array))

same for max

so you mean I have to create two different methods for this?? I am actually asked to write one method that will allow me to do both of these at the same time

[pm_kirkham]

but how do I find both the min and max at the same time and returning both at the same time??
From your assignment in the first post:
Your method should return a pair
In C++ there is a standard template class called 'pair', which does what you might expect:

using namespace std;

pair<int,int> find_limits (int* data, size_t length)
{
if (length > 0)
{
pair<int,int> limits(find_limits(data + 1, length - 1));

return make_pair(min(limits.first, *data), max(limits.second, *data));
}
else
{
return make_pair(*data, *data);
}
}

int main ()
{
int data[] = { 4, 2, 0, 9, 8 };

pair<int, int> limits(find_limits(data, sizeof(data)/sizeof(int)));

cout << limits.first << ", " << limits.second << std::endl;
}


Though since I've also seen this exact same question asked in a Java forum, perhaps you should say what you have to work in rather than asking how, as each language has different idioms for returning multiple values.

[-EquinoX-]

what if I just have to write a pseudo code for this problem, therefore I don't have to worry about which programming language I am using. I haven't been introduced yet to java, so this I can't use C

here's some kind of the pseudo code that I come up with, what do you guys think?? and I think this runs in the order of O(n).. please do correct me if I am wrong:


int a[N]; // array

int maxmin (A[])
{
if (|A| == 2) { // A = (a,b}
if (a > b) return(a,b);
else return(b,a);
}
Split A into two parts: A1, A2;
(max1,min1) = maxmin(A1);
(max2,min2) = maxmin(A2);
if (max1 > max2) max = max1;
else max = max2;
if (min1 < min2) min = min1;
else min = min2;
return(max,min);
}

}

[CMPITG]

so you mean I have to create two different methods for this?? I am actually asked to write one method that will allow me to do both of these at the same time
No, my two methods are ONE, one's written in C and one's written in C++. In that method, do one work for both min and max.

[bobtheclown]

what if I just have to write a pseudo code for this problem, therefore I don't have to worry about which programming language I am using. I haven't been introduced yet to java, so this I can't use C

here's some kind of the pseudo code that I come up with, what do you guys think?? and I think this runs in the order of O(n).. please do correct me if I am wrong:


int a[N]; // array

int maxmin (A[])
{
if (|A| == 2) { // A = (a,b}
if (a > b) return(a,b);
else return(b,a);
}
Split A into two parts: A1, A2;
(max1,min1) = maxmin(A1);
(max2,min2) = maxmin(A2);
if (max1 > max2) max = max1;
else max = max2;
if (min1 < min2) min = min1;
else min = min2;
return(max,min);
}

}

I see what you are trying to do here, and it looks good to me, except you don't handle where the passed array has an odd number of values. You will need to add a base case for size 1 (just return the same number for min and max), as well as code the split of the array to put the odd member on one side or the other. Otherwise I think this algorithm will work fine. It looks to me like this does run on the order of O(n).

You will obviously need to clean this up a bit before turning it in and actually code where you have "Split A into two parts: A1, A2". As I am assuming based on prior posts that you are in McCann's 345 class, I would also recommend making your pseudocode less code-like (as it is just "pseudo" code). There is a pseudocode style guide on page 8 of Algorithm Design.