java - 二分查找CompareTo Java

标签 java sorting recursion binary-search compareto

我正在尝试对对象数组使用二分搜索。我使用对象是因为在一个实例中我可能有一组字符串或整数。我目前正致力于实现我的 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”或任何我放在第二个可比较而不是字符串的参数。另外,如果我将对象转换到名称前面,它只会将其识别为对象而不是对象[]。
谢谢。

最佳答案

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

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方法因为 StringInteger已经实现Comparable .

我替换了ObjectT (其中 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 - 二分查找CompareTo Java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29356436/

相关文章:

matlab - 从向量中提取值并根据其原始序列对它们进行排序

mysql - 这是一个 MySQL 排序错误吗?

python - Django 管理员 : Ordering of ForeignKey and ManyToManyField relations referencing User

ruby - Ruby 中的递归文件列表

recursion - 您将如何在 Prolog 中编写程序以使用递归打印从 1 到 10 的数字?

java - 如何在 Java 中将 Map<String, Set<String>> 转换为 Map<String, String[]>

java - 以编程方式更改系统亮度

python-3.x - 如何使用 python 生成器递归生成对象?

java - 复合对象如何与父对象通信?

java - 测试空白时抛出异常