java - 尝试执行通用二进制搜索时，方法不能应用于给定类型

Question

假设我有一个名为 RandomObject 的类:

public class RandomObject implements Comparable<RandomObject> {

    private String name;
    private int value;

    public RandomObject(String name, int value) {
        this.name = name;
        this.value = value;
    }

          . 
          .
          .

    public int compareTo(RandomObject rn) {
        return Integer.compare(value, rn.value);
    }

还有这个 RandomObject 数组(每个对象都保存一个随机 int 值，用于比较目的):

RandomObject[] arr = new RandomObject[10];
for (int i = 0; i < arr.length; ++i) {
        arr[i] = new RandomObject(" ", (int) (Math.random() * 50));
    }

我还有一个名为 Quicksort 的类，其中包含以下排序方法:

public static <T extends Comparable<? super T>> void sort(T[] a) {
    sort(a, 0, a.length - 1);
}

 public static <T extends Comparable<? super T>> void sort(T[] a, int start, int end) {
    int left = start, right = end;
    T pivot = a[(left + right) / 2];

    do {
        while (a[left].compareTo(pivot) < 0) {
            left++;
        }
        while (a[right].compareTo(pivot) > 0) {
            right--;
        }
        if (left <= right) {
            T temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }
    } while (left <= right);

    if (start < right) {
        sort(a, start, right);
    }
    if (left < end) {
        sort(a, left, end);
    }
}

调用 Quicksort.sort(arr) 正常工作并按值对 arr 进行排序。

但是，我还有一个 BinarySearch 类，它具有以下 search 方法:

public static <T extends Comparable<? super T>> int search(T[] a, T value) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start + (end - start) / 2;
        if (a[mid].compareTo(value) == 0) {
            return mid;
        } else if (a[mid].compareTo(value) > 0) {
            end = mid;
        } else {
            start = mid + 1;
        }
    } while (start < end);
    return -1;
}

当我尝试执行这样的搜索时:

Integer x = 2;
System.out.println("Trying to find x: " + BinarySearch.search(arr, x));

出了点问题:

"java: method search in class br.com.algorithms.BinarySearch cannot be applied to given types;
required: T[],T
found: br.com.algorithms.RandomObject[],java.lang.Integer
reason: inference variable T has incompatible bounds
lower bounds: br.com.algorithms.RandomObject,java.lang.Integer,java.lang.Comparable<? super T>
lower bounds: java.lang.Integer,br.com.algorithms.RandomObject"

no instance(s) of type variable(s) exist so that RandomObject conforms to an Integer

在这种情况下，我很难理解为什么 sort 方法有效而 search 方法无效。如果这两种方法都需要 T[] 并且我为这两种情况提供了 RandomObject[]，为什么不编译搜索？这到底有什么区别？

Answer 1

What's exactly the difference here?

search需要 T[]和一个 T ，这意味着第一个参数的数组元素类型需要与第二个参数的类型相同。你给了RandomObject[]和 Integer , 这显然是无效的。

另一方面，sort只需要一个T[] , 所以你可以给它任何引用类型的数组，并且 参数之间没有进一步的限制。毕竟，只有一个参数。

请注意，不可能在 RandomObject[] 中搜索整数与您当前的实现。这是因为 compareTo比较 RandomObject 的实例.它不比较RandomObject反对Integer

您可以做的是创建一个“虚拟”RandomObject使用 x , 并将其传递给 search :

int x = 1;
RandomObject key = new RandomObject("this does not matter", x);
System.out.println("Trying to find x: " + BinarySearch.search(arr, key));

您还可以创建 search 的非通用版本只搜索 RandomObject[] .在这个非通用版本中，您可以将第二个参数更改为 int :

public static int search(RandomObject[] a, int value) { ... }

但是在泛型方法中，很难知道调用者想通过什么键来搜索。但这并非不可能 - 您可以创建这样的界面:

interface BinarySearchableByKey<T extends Comparable<? super T>> {
    T getKey();
}

代替(或除此之外)实现 Comparable , RandomObject应该实现 BinarySearchableByKey<Integer> ，因为它可以通过整数键搜索。

public class RandomObject implements BinarySearchableByKey<Integer> {
    // ...

    @Override
    public Integer getKey() { return value; }
}

更改 search有两个类型参数——数组的类型和搜索键类型:

public static <K extends Comparable<? super K>, T extends BinarySearchableByKey<? extends K>> int search(T[] a, K value) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start + (end - start) / 2;
        if (a[mid].getKey().compareTo(value) == 0) {
            return mid;
        } else if (a[mid].getKey().compareTo(value) > 0) {
            end = mid;
        } else {
            start = mid + 1;
        }
    } while (start < end);
    return -1;
}