Compare elements in an array of string in Java

Question

I have to write a method that will compare elements in an array of strings and return the index of the largest element. It's going to be done recursively using a divide and conquer approach. I have an idea, and I was just looking to see if my idea was right or if it should be done in a different way.

I was planning on looking at the array from the left side to mid -1, then look at mid, and then look at mid +1 to right. I have a variable that will keep track of the largest index, and then after that make the recursive call for the left side and the right side.

Does that sound like a good way to approach this problem?

This is what I have so far:

public int longest()
{
    longest(0, a.length-1);
    return longestIndex;
}

private int longest( int left, int right)
{
    int longestIndex;
    int mid;

    if(left > right)
    {
        longestIndex = -1;
    }
    else if(left == right)
    {
        longestIndex = 0;
    }

    else
    {
        longestIndex = 0;

        mid = (left + right) / 2;
        longest(left, mid - 1);
        if (a[mid].compareTo(a[longestIndex]) > 0)
        {
            longestIndex = mid;
        }
        longest(mid + 1, right);            
    }            
    return longestIndex;
}

Also, since the methods are supposed to return an int, how would I pass the longestIndex n the private method up to the public method so that it would show up in my test program when longest is called?

NullUserException · Accepted Answer · 2011-09-29 17:26:21Z

4

Does it have to be recursive? Using recursion for this sounds like a case of:

And your recursion looks totally wrong anyways, because not only you are not keeping track of the actual index but also your base cases and recursive calls don't make any sense.

If I were compelled to use recursion, I would do something like:

int longest(array):
    return longest_helper(0, 0, array)

int longest_helper(max_index, curr_idx, array):
    # base case: reached the end of array
    if curr_idx == array.length:
        return max_index

    if array[curr_idx].length > array[max_index].length:
        max_index = curr_idx

    # recursive call
    return longest_helper(max_index, curr_idx + 1, array)

And then I would proceed to drop the class and tell the professor to give students problems where recursion is actually helpful next time around.

Since it doesn't look like the array is sorted, the easiest (and fastest) way to do this would just be go through the whole thing (pseudocode):

max_index  = 0
max_length = array[0].length

for index in 1 .. array.length:
    if array[index].length > max_length:
        max_length = array[index].length
        max_index  = index

return max_index

edited Sep 29, 2011 at 17:26

answered Sep 29, 2011 at 16:50

NullUserException

85.8k31 gold badges212 silver badges239 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Andrew Thompson Over a year ago

Huh. I did not even realize that a combined image/link was supported on SO! It would be great if the styles/HTML could make the image link more obvious (as being a link).

alexthefourth Over a year ago

has to be recursive unfortunately

Miserable Variable · Accepted Answer · 2011-09-29 17:23:20Z

0

This is your fourth question in two days on recursion. It is good that you are putting homework tag but your time would be better spent understanding how recursion works.

My recommendation is to take a few colored discs (poker chips or playing cards of a single suite work well), work out manually the recursive solution to Towers of Hanoi and then come back and look at the individual questions you have been asking.

In all likelihood you will be able to answer all the questions yourself. You would also be able to accept the answers, increasing you chances in future of getting responses when you face tougher questions.

answered Sep 29, 2011 at 17:23

Miserable Variable

28.8k15 gold badges79 silver badges138 bronze badges

2 Comments

alexthefourth Over a year ago

yeah i know, ive been having trouble seeing how the recursive calls work and when they are called.

Miserable Variable Over a year ago

That is why my sincere advice above. You need to figure out the basics.

Collectives™ on Stack Overflow

Compare elements in an array of string in Java

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related