This week's book giveaway is in the Other Languages forum.We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# finding a max number via a recursive method

Ranch Hand
Posts: 112
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 ]

Jamie Robertson
Ranch Hand
Posts: 1879
[solution deleted]
never mind, missed the keyword "recursive"!
Jamie
[ September 06, 2002: Message edited by: Jamie Robertson ]

Anthony Villanueva
Ranch Hand
Posts: 1055
Can't you use max() of the Math class?

Norm Miller
Ranch Hand
Posts: 56
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 ]