尝试执行通用二分搜索时，方法无法应用于给定类型

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

这个RandomObjects 数组（每个数组都保存一个随机 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：类 br.com.algorithms.BinarySearch 中的方法搜索无法应用于给定类型；
必需：T[],T
找到：br.com.algorithms.RandomObject[],java.lang.Integer
原因：推理变量 T具有不兼容的边界
下限：br.com.algorithms.RandomObject,java.lang.Integer,java.lang.Comparable<? super T>
下限：java.lang.Integer,br.com.algorithms.RandomObject"

不存在类型变量的实例，因此 RandomObject 符合 Integer

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

Answer 1

这里到底有什么区别？

search接受 aT[]和 a T，这意味着第一个参数的数组元素类型需要与第二个参数的类型相同。您已经给出了RandomObject[]和Integer，这显然是无效的。

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

RandomObject[]请注意，使用当前的实现不可能在 a 中搜索整数。这是因为compareTo比较 的实例RandomObject。它不会将RandomObjects 与Integers 进行比较。

相反，您可以做的是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;
}