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. */

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'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 ]

michael bradly
Ranch Hand

Joined: Oct 06, 2000
Posts: 112

posted

0

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