finding a max number via a recursive method

[michael bradly]

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]

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

[Anthony Villanueva]

Can't you use max() of the Math class?

[Norm Miller]

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

 
public class G 
{
public G(){  };

public int FindMax( int[]Ar, int lo, int hi)
{  
   assert(lo <= hi);
   if (lo == hi)   return Ar[lo];   // One element, so return it
   int sublength = (hi+1 - lo)/2;
   assert (sublength > 0);
   
   int maxa = FindMax( Ar, lo, lo + sublength-1);
   int maxb = FindMax( Ar, lo + sublength, hi);
   return Math.max(maxa, maxb);
}


  public static void main(String[] args) {
    G BinMax = new G();
    int[]iA = {55, 33, 100, 66};
    
    System.out.println( BinMax.FindMax( iA,  0, iA.length-1 ));
  }
} 

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

[michael bradly]

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

[Recaip Sanli]

Good news, I came up with super compact answer working on improving a snippet I found.

Thank you for everyone! I truly appreciate every single try and input. I do agree with many of you on writing future in mind and ease of understanding later on!

       if (pos == arr.length) {
           return arr[arr.length-1];
       } else {
           return Math.max(arr[pos], largestRec(arr, ++pos));
       }

Test

Test 3: largest(10) ==> [Passed]
 Expected: 10
 Yours: 10

Test 4: largest(10, 20, 30, 40, 50, 60) ==> [Passed]
 Expected: 60
 Yours: 60

Test 5: largest(70, 20, 30, 40, 50, 10) ==> [Passed]
 Expected: 70
 Yours: 70

Test 6: largest(70, 20, 100, 40, 50, 10) ==> [Passed]
 Expected: 100
 Yours: 100

[Junilu Lacar]

It's good to see you found a solution.  As we were saying in the other thread you started though, using pos+1 is preferable to ++pos.  Either expression works but ++pos modifies the value of pos when there's really no need to do so; pos+1 is clearer and does only what you'd expect the program to do.