jQuery in Action, 2nd edition*
The moose likes Java in General and the fly likes finding a max number via a recursive method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "finding a max number via a recursive method" Watch "finding a max number via a recursive method" New topic

finding a max number via a recursive method

michael bradly
Ranch Hand

Joined: Oct 06, 2000
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

Joined: Jul 09, 2001
Posts: 1879

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

Joined: Mar 22, 2002
Posts: 1055
Can't you use max() of the Math class?
Norm Miller
Ranch Hand

Joined: May 21, 2002
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 ]
michael bradly
Ranch Hand

Joined: Oct 06, 2000
Posts: 112
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
subject: finding a max number via a recursive method
Similar Threads
max and min in array?
Drawing a Histogram ( I know its been covered and I have read through those posts)
Any suggestions on making this code work?
Variable scope and assignment
double precision floating point