1 2 Previous Next 18 Replies Latest reply: Feb 21, 2008 1:37 AM by 807601

# Recursivley Find A Max Number in an Array

Hello everyone,

My goal: Given an array of numbers, I want to recursively use Divide & Conquer method, search that array for the biggest number in it, and then return the index of that number. Ex:

given: array = { 1, 9, 2, 3, 1, 7, 6, 4 };
int maxNumIndex = max_index(array, leftIndex, rightIndex);

maxNumIndex would be 1.

Here is what I have so far, and I'm not sure if this is the right way to go about doing this. I figure I need to compare the number at the MaxIndex, see if that is > or <, then set the maxNumberIndex equal to whatever the MaxIndex was.

This is what I have (remember I'm using Divide & Conquer):
``````// Return the max num's index using divide and conquer
//args being passed in:  a = the array, lf = left Index, rt = the right Index.
private static int max_index(int a[], int lf, int rt)
{
int maxNumberIndex;
int mid = (rt + lf) / 2;
maxNumberIndex = a[mid];
int rightMaxIndex = max_index(a, mid + 1, rt);
int leftMaxIndex = max_index(a, lf, mid - 1);
if (lf == rt)
{
maxNumberIndex = lf;
}

else if ((a[leftMaxIndex] > a[rightMaxIndex]) &&     (a[leftMaxIndex] > a[mid]))
{
maxNumberIndex = leftMaxIndex;
}
else if ((a[rightMaxIndex] > a[leftMaxIndex]) && (a[rightMaxIndex] > a[mid]))
{
maxNumberIndex = rightMaxIndex;
}
if ((a[mid] > a[leftMaxIndex]) && (a[mid] > a[rightMaxIndex]))
{
maxNumberIndex = mid;
}
else if ((a[mid] == a[rightMaxIndex]) && (a[leftMaxIndex] == a[rightMaxIndex]))
{
maxNumberIndex = mid;
}

return maxNumberIndex;          //RETURN OUR MAX NUMBER INDEX
}``````
Thoughts?
• ###### 1. Re: Recursivley Find A Max Number in an Array
Thoughts?

%
• ###### 2. Re: Recursivley Find A Max Number in an Array
This is different from the rest, fellow.
• ###### 3. Re: Recursivley Find A Max Number in an Array
How so?

%
• ###### 4. Re: Recursivley Find A Max Number in an Array
What do you mean 'thoughts'? Does that code work or not? Do you have any questions, or is this just a show and tell?
• ###### 5. Re: Recursivley Find A Max Number in an Array
I see something that resembles a stopping condition.

My biggest beef is that you don't bother to include this as part of a Java class that somebody might have a hope of compiling and running. A test case would be nice.

I'm pretty tired of students posting their stuff here and asking for "thoughts". Please do enough work to ask a straight question.

Does this compile? Good. If not, fix the errors.

Does it run? If so, does it perform the behavior as expected? If not, could you please show what the behavior is?

http://catb.org/~esr/faqs/smart-questions.html

%
• ###### 6. Re: Recursivley Find A Max Number in an Array
Here's a thought: I think this code sucks @ss.

%
• ###### 7. Re: Recursivley Find A Max Number in an Array
1) No it does not compile. I receive a stack overflow on:

``int mid = (rt + lf) / 2;``
2) Students? Who cares if I am a student or not, either help or don't. I was under the assumption this was a forum for help.

3) It's a large class file, I didn't want to bog down the post with a page of code, and I'm not sure that is the correct way to post problems. If you just glaze your eyes over my name, you'll see that my account was registered yesterday. If I trim it down will you still rant against my thread?

Here:
``````class recursive
{
// make array one smaller from the right end
public static void testMaxIndex(int a[])
{
System.out.println("The max index num is: ");
System.out.println(max_index(a, 0, a.length - 1));
}

// Return the max num's index using divide and conquer
private static int max_index(int a[], int lf, int rt)
{
int maxNumberIndex;
int mid = (rt + lf) / 2;
maxNumberIndex = a[mid];               //Stack Overflow here.
int rightMaxIndex = max_index(a, mid + 1, rt);
int leftMaxIndex = max_index(a, lf, mid - 1);
if (lf == rt)
{
maxNumberIndex = lf;
}

else if ((a[leftMaxIndex] > a[rightMaxIndex]) && (a[leftMaxIndex] > a[mid]))
{
maxNumberIndex = leftMaxIndex;
}
else if ((a[rightMaxIndex] > a[leftMaxIndex]) && (a[rightMaxIndex] > a[mid]))
{
maxNumberIndex = rightMaxIndex;
}
if ((a[mid] > a[leftMaxIndex]) && (a[mid] > a[rightMaxIndex]))
{
maxNumberIndex = mid;
}
else if ((a[mid] == a[rightMaxIndex]) && (a[leftMaxIndex] == a[rightMaxIndex]))
{
maxNumberIndex = mid;
}

return maxNumberIndex;
}
}``````
Specific Question_: Is the base case not being reached, and how do I fix this such that the base case is reached?
• ###### 8. Re: Recursivley Find A Max Number in an Array
cafebabe.java wrote:
1) No it does not compile. I receive a stack overflow on:

``int mid = (rt + lf) / 2;``
The compiler has a stack overflow? Must contact Sun.
• ###### 9. Re: Recursivley Find A Max Number in an Array
cafebabe.java wrote:
1) No it does not compile. I receive a stack overflow on:

``int mid = (rt + lf) / 2;``
Stack overflow on compile? I don't think so. That's a runtime problem.

2) Students? Who cares if I am a student or not, either help or don't. I was under the assumption this was a forum for help.
It is, as long as the person seeking help asks good questions.

Ultimately, you're responsible for fixing problems. This can be a good place for advice, but you seem to be extraordinarily passive.

Students are notorious for doing a poor job of it. Your efforts so far seem very student-esque to me. Looks like homework that you can't make work.
3) It's a large class file,
To sort an array recursively? I doubt it. You're doing a bad job of isolating your problem.
I didn't want to bog down the post with a page of code, and I'm not sure that is the correct way to post problems. If you just glaze your eyes over my name, you'll see that my account was registered yesterday. If I trim it down will you still rant against my thread?
I'll still rant if you do a poor job.
Specific Question_: Is the base case not being reached, and how do I fix this such that the base case is reached?
I don't know. Can you run this in a debugger, step through, and see what's happening? That's what a poor developer would do.

%
• ###### 10. Re: Recursivley Find A Max Number in an Array
To hell with it, I've gotten more productive work done outside this thread than I have responding to assholes like you (baftos, duffymo).

Are all Java developers like this? After all this is the New to Java forum. Seems I need learn programming in something other than Java then!

I never mentioned sorting an array, thats your assumption.

Oh well, forget about it. Go bash on someone else who is new to Java in this forum duffy, I'm done with BS like this. There's more ad hominem being thrown around in here than there are productive sentences being formed.
• ###### 11. Re: Recursivley Find A Max Number in an Array
This here forum is real friendly: http://saloon.javaranch.com/cgi-bin/ubb/ultimatebb.cgi
• ###### 12. Re: Recursivley Find A Max Number in an Array
cafebabe.java wrote:
To hell with it, I've gotten more productive work done outside this thread than I have responding to assholes like you (baftos, duffymo).
Nobody asked you to respond. If you don't get what you want here, feel free to go elsewhere. Or don't come back. You won't be missed.
Are all Java developers like this? After all this is the New to Java forum. Seems I need learn programming in something other than Java then!
Who cares?
Oh well, forget about it. Go bash on someone else who is new to Java in this forum duffy, I'm done with BS like this. There's more ad hominem being thrown around in here than there are productive sentences being formed.
Fine. See ya, meat. Go learn recursion somewhere else.

Thoughts?

%
• ###### 13. Re: Recursivley Find A Max Number in an Array
cafebabe.java wrote:
To hell with it, I've gotten more productive work done outside this thread than I have responding to assholes like you (baftos, duffymo).

Are all Java developers like this? After all this is the New to Java forum. Seems I need learn programming in something other than Java then!

I never mentioned sorting an array, thats your assumption.

Oh well, forget about it. Go bash on someone else who is new to Java in this forum duffy, I'm done with BS like this. There's more ad hominem being thrown around in here than there are productive sentences being formed.
If you don't have a clue how to fix this why not ask your teacher or classmates?
• ###### 14. Re: Recursivley Find A Max Number in an Array
We understand that you're new to Java. But new to the language doesn't mean new to how to get help in general. Technical forums are not Doctor's offices, and are not Auto Repair shops. In those places you can say "it's broke, help!" and the doctor/mechanic, knowing exactly what the purpose of the broken item is, can help fix it. Plus, they get paid.

Here, we don't get paid. Also, we don't know exactly what your code is supposed to do, separating us from doctors and mechanics, who know what organs and parts are supposed to do. Here, we need a little more information. Don't say "it doesn't work", post the exact error messages received, and exactly what input made the error occur. Don't post just the method the problem occurred in, post the entire class. And if your class is too big, it's your job to cut it down to a more manageable size, that still compiles. If you want a quick answer, you aren't going to get it if we have to spend 20 minutes deciphering what your goal is, or trying to make your code compile by removing all references to classes that you didn't give us.