Java比较对象

Question

我正在尝试创建一个二进制搜索程序，该程序可以使用各种类型的变量（int、float、string等）来查看数组中是否存在元素。我正试图找出如何比较变量。下面是我正在使用的内容的草图：

import java.util.ArrayList;

class BinarySearch{
//Receives the list as the first argument, and the number to search
// for as the second argument.
public static boolean binarySearch(Object list[], Object target) {
    int listLen = list.length;
    int min = 0;
    int max = list.length - 1;
    //execute the binary search
    while (true) {
        int guess = (min + max / 2);
        if(target.equals(list[guess])) return true;

        if(list < target) {       //What to do here?
            //do some stuff

        ...  

我甚至不确定使用对象是否是最好的方法。

Answer 1

为输入参数使用泛型类型，并使输入参数包含比较器，以便用户可以完全控制如何比较传入的任何类型的输入。

签名看起来像

public static <T> int binarySearch(
    T[] list, T target, java.util.Comparator<? super T> comparator) 

这比让对象实现可比较要好，因为在不同的情况下，对象可能必须以不同的方式进行排序。如果使用Comparable，则只能使用由要比较的内容实现的方式，但是使用Comparable的搜索可以为输入列表的每种不同排序方式传入不同的比较器。

你的比较就变成了

int compareResult = comparator.compare(target, list[guess]);

其中结果为0表示2个对象相等，负结果表示第一个参数小于第二个参数，正结果表示第一个参数大于第二个参数。

检查您如何计算中点，您的代码由于运算符优先级的工作方式而中断。如果不小心，对于大数组（大于Integer.MAX\u值的一半）也可能会遇到问题。

Answer 2

我们可以使用Collections.binary搜索（...）方法从java集合api，除非我错过了什么。

Answer 3

您不应该使用对象，您需要使用泛型类或方法-在我的示例中，我使用第二个，因为您的方法是静态的：

public class BinarySearch
{
    public static <T> boolean Run(T[] list, T target)
    {
    }
}

如果您需要比较值，您可以使用可比

将此对象与指定对象进行顺序比较。当此对象小于、等于或大于指定对象时，返回负整数、零或正整数。

让我们使T可比较

public class BinarySearch
{
  public static <T extends Comparable<T>> boolean Run(T[] list, T target)
  {
    int listLen = list.length;
    int min = 0;
    int max = list.length - 1;

    while (true) {
        int guess = (min + max / 2);
        if (target.equals(list[guess])) return true;

        if (list[guess].compareTo(target) < 0) { 
            // list[guess] is less than target
        } else {
            // list[guess] is larget than target
        }
    }
}

由于大多数Java类都扩展了可比较，现在，您可以执行以下操作：

Integer[] ints = { 1, 2, 3, 4, 5, 6, 7, 8, 10, 25, 30, 50, 100 };
System.out.println(BinarySearch.Run(ints, 25));
// recognized as: System.out.println(BinarySearch.<Integer>Run(ints, 25));

String[] strings = {"a", "b", "c", "d", "e"};
System.out.println(BinarySearch.Run(strings, "c"));
// recognized as: System.out.println(BinarySearch.<String>Run(strings, "c"));

您还可以在BinarySearch中使用任何自定义类，如果它扩展了可比