Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

finding a max number via a recursive method

 
michael bradly
Ranch Hand
Posts: 112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
MySQL Database Suse
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[solution deleted]
never mind, missed the keyword "recursive"!
Jamie
[ September 06, 2002: Message edited by: Jamie Robertson ]
 
Anthony Villanueva
Ranch Hand
Posts: 1055
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can't you use max() of the Math class?
 
Norm Miller
Ranch Hand
Posts: 56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic