programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# finding a max number via a recursive method

michael bradly
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 ]

michael bradly
Ranch Hand
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

Recaip Sanli
Ranch Hand
Posts: 69
2
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!

Test

Junilu Lacar
Sheriff
Posts: 11169
160
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.

 Don't get me started about those stupid light bulbs.