# finding a max number via a recursive method

michael bradly

Ranch Hand

Posts: 112

posted 14 years ago

I am trying to work on a problem in which I have to find the max number in an array by dividing the array in two, then find the largest int in each half, then find the largest of the two. I understand most of the concepts, but am having trouble bringing them all together.

Here is what I think I know...

myArray (int[] anArray, first, last, maxValue)

{

// base case

if (the array only has one value)

return maxValue = anArray[0];

/* Question #1: Since I am going to have to compare two ints, do I need a second base case? i.e.:

else if (there are 2 values to compare)

if (maxLeftArray == maxRightArray)

assign to maxValue either one

else if (maxLeftArray < maxRightArray)

assign to maxValue maxRightArray

else if (maxLeft > maxRight)

assign to maxValue maxLeftArray

*/

else (find the midpoint in the array)

midpoint = (first + last)/2;

/*Question 2: How to deal with the midpoint?

For sake of argument, these values are in the array {12, 5, 6, 7, 15, 20}

Now the midpoint is [3] which is 6.

So now I have {12, 5} midpoint of 6 and {7, 15, 20}. Since I am unsure as to the merits of question 1, I'll deal with this as I understand it.

*/

myArray(int[] anArray, first, midpoint -1, maxValue)

if (midpoint > anArray[first+1])

maxLeftArray = midpoint;

// my assumption is that when there are only two

//subidexes left, the midpoint is [0] and what

//it is being compared to is [1]

else maxLeftArray = anArray[first+1];

myArray (int[] anArray, midpoint +1, last, maxValue)

if (midpoint +1 < anArray[last])

maxRightArray = anArray[last];

else maxRightArray = midpoint +1;

// or can I include the midpoint in the left side

// (int[] an Array, first, midpoint???, maxValue)

As may be evident, I am confused. Any suggestions or helpful web references would be appreciated.

Regards, Michael

[ September 05, 2002: Message edited by: michael bradly ]

Here is what I think I know...

myArray (int[] anArray, first, last, maxValue)

{

// base case

if (the array only has one value)

return maxValue = anArray[0];

/* Question #1: Since I am going to have to compare two ints, do I need a second base case? i.e.:

else if (there are 2 values to compare)

if (maxLeftArray == maxRightArray)

assign to maxValue either one

else if (maxLeftArray < maxRightArray)

assign to maxValue maxRightArray

else if (maxLeft > maxRight)

assign to maxValue maxLeftArray

*/

else (find the midpoint in the array)

midpoint = (first + last)/2;

/*Question 2: How to deal with the midpoint?

For sake of argument, these values are in the array {12, 5, 6, 7, 15, 20}

Now the midpoint is [3] which is 6.

So now I have {12, 5} midpoint of 6 and {7, 15, 20}. Since I am unsure as to the merits of question 1, I'll deal with this as I understand it.

*/

myArray(int[] anArray, first, midpoint -1, maxValue)

if (midpoint > anArray[first+1])

maxLeftArray = midpoint;

// my assumption is that when there are only two

//subidexes left, the midpoint is [0] and what

//it is being compared to is [1]

else maxLeftArray = anArray[first+1];

myArray (int[] anArray, midpoint +1, last, maxValue)

if (midpoint +1 < anArray[last])

maxRightArray = anArray[last];

else maxRightArray = midpoint +1;

// or can I include the midpoint in the left side

// (int[] an Array, first, midpoint???, maxValue)

As may be evident, I am confused. Any suggestions or helpful web references would be appreciated.

Regards, Michael

[ September 05, 2002: Message edited by: michael bradly ]

Anthony Villanueva

Ranch Hand

Posts: 1055

Norm Miller

Ranch Hand

Posts: 56

posted 14 years ago

Here's an example to study. You can see how the code keeps breaking the array in pieces about half as big as the input array. There is a test to stop when the array is only one element.

(The code breaks if you start with iA[] = {} so either don't do that or fix it.)

(If you aren't using the 1.4 release, you can omit the asserts.)

[ September 06, 2002: Message edited by: Norm Miller ]

[ September 06, 2002: Message edited by: Norm Miller ]

(The code breaks if you start with iA[] = {} so either don't do that or fix it.)

(If you aren't using the 1.4 release, you can omit the asserts.)

[ September 06, 2002: Message edited by: Norm Miller ]

[ September 06, 2002: Message edited by: Norm Miller ]

michael bradly

Ranch Hand

Posts: 112

posted 14 years ago

Thanks for the responses. The main issue is that I am taking a class in algorithms/data structures, so regardless of what inherent features the various JDK's have to deal with finding a max, I must use a recursive method to find the max.

My personal problem with such situations is that I extrapolate my thought processes as to how a computer deals with a situation, and not only do I find myself thinking too much about the problem, but I also end up thinking incorrectly as to how a computer would deals with it since a computer tends to be much more efficient than my thoughts.

Essentially the code I listed deals with how my brain is dealing with the situation and I am seeking guidance as to how a computer deals with recursive solutions in regards to finding a max number in an unsorted array.

Althought I am implementing the solution in Java, I am not so much looking for the simplest way to do it in Java, rather I am looking for a way to do it in a language netural manner so I can come to a better understanding of recursion. (Although I really want to do it in JAVA!!!)

I've had to much to drink!

Regards, Micahel

My personal problem with such situations is that I extrapolate my thought processes as to how a computer deals with a situation, and not only do I find myself thinking too much about the problem, but I also end up thinking incorrectly as to how a computer would deals with it since a computer tends to be much more efficient than my thoughts.

Essentially the code I listed deals with how my brain is dealing with the situation and I am seeking guidance as to how a computer deals with recursive solutions in regards to finding a max number in an unsorted array.

Althought I am implementing the solution in Java, I am not so much looking for the simplest way to do it in Java, rather I am looking for a way to do it in a language netural manner so I can come to a better understanding of recursion. (Although I really want to do it in JAVA!!!)

I've had to much to drink!

Regards, Micahel