1

So, I am in a course to learn java, and I'm learning about sorting, searching, algorithms, and generics. I am trying to recreate a binary search method/class that accepts any type of Comparable object (like the ArrayList<Type>).

I understand how to do it with ints, but I dont really know how to go about it with non-primitive types. This is what I assume it should roughly look like:

public class Objects<T> implements Comparable //I'm not sure about this,
//but I need to call compareTo() to compare the objects?
{
    /**
     * called from other program to find an element index in an array
     */
    public static int binSearchAll(T find, T array[])
    {
        return binarySearch(array, 0, (array.length)-1, find);
    }

    public static int binarySearch(T array[], int lower, int upper, T X)
    //x is the element to find
    {
        if (upper < lower)
            return -1;
        int middle = (lower + upper) / 2;
        if (array[middle].compareTo(X))
            return middle;
        if (array[middle] < X)
            return binarySearch(a, middle+1, upper, X);
        else
            return binarySearch(a, lower, middle-1, X);
    }
}

I tried to figure out how to make this work, but I'm at a loss. In the int version, it works, but then it's only for integer types and doesn't accept double or string types as the problem asks.

in the driver class, I want to be able to create a new object and use it like this:

String[] str = {"a", "b", "c"};
Objects<String> s = new Objects<String>();
int indexOfB = s.binSearchAll("b", str);

or, if it's possible, like this:

String[] str = {"a", "b", "c"};
int indexOfB = Object<String>.binSearchAll("b", str);

The exact wording of the problem is:

Create an ObjectBinarySearcher class that can search an array of Comparable objects. Demonstrate the class in a program that searches for a String in an array of String objects.

I'm almost sure I'm overthinking this.

Thanks for any help you can give!

4

3 回答 3

1

These two lines are the problem:

if (array[middle].compareTo(X))
...
if (array[middle] < X)

... compareTo returns an int rather than a boolean, and you can't use < on arbitrary types. I suspect you've realized that much, but I'll just give you a hint: read the Comparable.compareTo documentation. You need to use compareTo instead of <... read the documentation for the return value to work out what you need to do.

(You probably just want to call compareTo once, and then check the result twice. There are three possibilities to consider, as documented...)

于 2013-03-30T17:00:43.420 回答
0

You need that your template class T implements the Comparable interface. Your actual code means that only your Objects class implement the interface. You must turn

public class Objects<T> implements Comparable {
    //class content...
}

Into

public class Objects<T extends Comparable<T>> {
    //class content...
}

And also, follow the advice from JonSkeet's answer about compareTo method.

于 2013-03-30T17:00:58.153 回答
0

You need that your template class T implements the Comparable interface. Your actual code means that only your Objects class implement the interface. You must turn

public class Objects<T> implements Comparable {
    //class content...
}

Into

public class Objects<T extends Comparable<T>> {
    //class content...
}

Luiggi Mendoza

And...

These two lines are the problem: if (array[middle].compareTo(X)) ... if (array[middle] < X) ... compareTo returns an int rather than a boolean, and you can't use < on arbitrary types. I suspect you've realized that much, but I'll just give you a hint: read the Comparable.compareTo documentation. You need to use compareTo instead of <... read the documentation for the return value to work out what you need to do.

(You probably just want to call compareTo once, and then check the result twice. There are three possibilities to consider, as documented...) Jon Skeet

Thanks for the answers. combined, I managed to get the program working. It now works with:

String[] str = {"a", "b", "c"};
Objects<String> s = new Objects<String>();
int indexOfB = s.binSearchAll("b", str);
于 2013-04-01T04:45:50.563 回答