二进制搜索比较 Java

Question

我正在尝试对对象数组使用二进制搜索。我使用对象是因为在一个实例中我可能有一组字符串或 ints。我目前一直在实施我的 compareTo 方法，不确定下一步是什么。这是我目前所拥有的 -

public static int binarySearch(Object[] items, Comparable target, int first, int last){

    if(first > last)
        return -1; // Base case for unsuccessful search
    else{
        int middle = (first + last) / 2; // Next probe index.
        int compResult = target.compareTo(items[middle]);
        if(compResult == 0)
            return middle; // Base case for unsuccessful search.
        else if (compResult <0)
            return binarySearch(items, target, first, middle -1);
        else
            return binarySearch(items, target, middle + 1, last);
    }
}
public static int binarySearch(Object[] items, Comparable target){
    return binarySearch(items, target, 0, items.length -1);
}
@Override
public int compareTo(T obj) {

    return 0;
}
public static void main(String[] args){
String[] names = {"Caryn", "Debbie", "Dustin", "Elliot", "Jacquie", "Jonathan", "Rich"};

    int myName = binarySearch(names, "Dustin");

我在调用 binarySearch 时遇到错误，它说 FiveThree 类型的方法 binarySearch(Object[], Comparable) 不适用于参数 (String[], String)。我知道它是因为我的 CompareTo 现在是空的，但我不知道如何使 "Dustin" 或我放在第二位的任何参数成为 Comparable 而不是字符串。此外，如果我在名称前面投射对象，它只会将其识别为对象而不是对象[]。
谢谢。

Answer 1

您的解决方案基本上有效。

I'm trying to use a binary search on an Object Array. I'm using object because for one instance I may have a set of strings or ints

这表明您应该使用泛型，而不是 Object[]。如果这样做，您将不得不使用 Integer[] 而不是 int[] 因为 Java 泛型不适用于原始类型。

没有必要编写 compareTo 方法，因为 String 和 Integer 已经实现了 Comparable.

我将 Object 替换为 T（其中 T extends Comparable<T>），它就起作用了。该程序按原样打印 2。

public static <T extends Comparable<T>> int binarySearch(T[] items, T target, int first, int last){

    if(first > last)
        return -1; // Base case for unsuccessful search
    else{
        int middle = (first + last) / 2; // Next probe index.
        int compResult = target.compareTo(items[middle]);
        if(compResult == 0)
            return middle; // Base case for unsuccessful search.
        else if (compResult <0)
            return binarySearch(items, target, first, middle -1);
        else
            return binarySearch(items, target, middle + 1, last);
    }
}

public static <T extends Comparable<T>> int binarySearch(T[] items, T target){
    return binarySearch(items, target, 0, items.length -1);
}

public static void main(String[] args) {
    String[] names = {"Caryn", "Debbie", "Dustin", "Elliot", "Jacquie", "Jonathan", "Rich"};

    int myName = binarySearch(names, "Dustin");
    System.out.println(myName);
}

二进制搜索比较 Java

Binary Search CompareTo Java

java

sorting

recursion

binary-search

compareto