如何在通用程序中实现二进制搜索对象数组？

因此，我正在学习java课程，并且正在学习排序，搜索，算法和泛型。我试图重新创建一个二分查找方法/类，它接受任何类型的Comparable对象（如ArrayList < 类型>）。如何在通用程序中实现二进制搜索对象数组？

我明白如何去做int s，但我真的不知道如何去处理它与非原始类型。这是我认为它应该大致是这样的：

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); 
    } 
}

我试图弄清楚如何使这项工作，但我不知所措。在int版本中，它可以正常工作，但只适用于integer类型，并且不会接受double或string类型，如问题所述。

在驱动程序类

，我希望能够创建一个新的对象，并使用它像这样：

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

或者，如果可能的话，像这样：

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

确切措辞的问题是：

创建一个ObjectBinarySearcher类，可以搜索Comparable对象的数组。在程序中演示该类，该程序在String 对象的数组中搜索字符串。

我几乎可以肯定，我正在推翻这一点。

感谢您的帮助！

来源

2013-03-30 user2005078

这两条线是问题：

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

... compareTo返回int，而不是boolean，你不能在任意类型使用<。我怀疑你已经意识到这一点，但我只是给你一个提示：阅读Comparable.compareTo文档。您需要使用compareTo而不是< ...请阅读返回值的文档以了解您需要执行的操作。

（你可能只是想打电话compareTo一次，然后检查结果的两倍。有三种可能性来考虑，如记录...）

来源

2013-03-30 17:00:43

谢谢，我没有阅读Comparable类的正确的文档，现在我工作。我认为它与Object.equals（）方法类似。 – user2005078

你需要你的模板类T实现Comparable接口。你的实际代码意味着只有你的Objects类实现了接口。您必须打开

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

进入

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

而且也遵循JonSkeet's answer约compareTo方法的建议。

来源

2013-03-30 17:00:58

谢谢，我只是在学习，所以我没有意识到发生了什么事情。我也很困惑，为什么当我调用compareTo（）方法时，我一直在收到错误，现在我明白它必须在类中被覆盖才能使用，除非数据类型已经覆盖它。我现在有它的工作。 – user2005078

@ user2005078因为你是新来的人，不要忘记标记最好的帖子作为答案，点击代表下方的检查。如果两个答案都满足你，你可以发布一个新答案并接受它。 –

，仍然无法正常工作。它需要'T延伸可比' – newacct

您需要您的模板类T实现可比较的接口。你的实际代码意味着只有你的Objects类实现了这个接口。您必须打开
public class Objects<T> implements Comparable { 
    //class content... 
} 
进入
public class Objects<T extends Comparable<T>> { 
    //class content... 
} 
Luiggi Mendoza

而且......

这两条线是问题：如果（数组[中]。 compareTo（X））... if（array [middle] < X）... compareTo返回int而不是布尔值，并且您不能在上使用<任意类型。我怀疑你已经意识到这一点，但我只是给你一个提示：阅读Comparable.compareTo文档。您需要以使用compareTo而不是< ...请阅读返回值的文档以确定您需要执行的操作。

（你可能只是想调用一次的compareTo，然后检查结果的两倍。有三种可能性要考虑，记录...） Jon Skeet

感谢您的答案。结合起来，我设法让程序工作。它现在的作品：

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

来源

2013-04-01 04:45:50 user2005078

如何在通用程序中实现二进制搜索对象数组？

回答

相关问题