为何泛型快排可处理RandomObject数组，泛型二分搜索传Integer却报错？

1. 定义的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);
    }
}

2. 创建RandomObject数组 #

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

3. 泛型快速排序类 #

public class 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)可正常按value排序数组。

4. 泛型二分搜索类 #

public class BinarySearch {
    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;
    }
}

5. 调用搜索时的编译错误 #

当执行以下代码时：

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[]，为什么search无法编译？两者的核心差异是什么？

核心差异：方法参数的类型约束 #

sort方法仅接收T[]类型参数，所有比较操作都是在同类型T的对象之间进行（比如a[left].compareTo(pivot)，其中pivot也是T类型）。当传入RandomObject[]时，编译器能直接推断出T为RandomObject，而RandomObject实现了Comparable<RandomObject>，完全满足<T extends Comparable<? super T>>的泛型约束，因此可以正常编译。

而search方法需要接收T[]和T两个参数，你传入的是RandomObject[]和Integer，编译器需要找到一个同时满足以下条件的T类型：

1. T是RandomObject的父类（适配数组参数）
2. T是Integer的父类（适配第二个参数）
3. T实现了Comparable<? super T>

但RandomObject和Integer没有符合要求的共同父类（Object是共同父类，但它未实现Comparable），因此编译器无法推断出合法的T类型，直接抛出编译错误。

为什么不能直接用Integer搜索？ #

本质上，RandomObject的compareTo方法只能接收RandomObject类型的参数，它并没有实现Comparable<Integer>接口。所以a[mid].compareTo(x)（x是Integer）本身就是语法错误，这也是编译器拒绝该调用的根本原因之一。

修复方案 #

要实现按value搜索，有两种常用方式：

1. 创建一个用于搜索的"探针"RandomObject实例，传入它作为搜索参数：

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

2. 修改二分搜索方法的泛型约束，支持传入可与T比较的参数，或者改用Comparator：

// 支持与T可比较的任意类型U
public static <T, U extends Comparable<? super T>> int search(T[] a, U value) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start + (end - start) / 2;
        int cmp = value.compareTo(a[mid]);
        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            end = mid;
        } else {
            start = mid + 1;
        }
    } while (start < end);
    return -1;
}

// 更灵活的Comparator方式
public static <T> int search(T[] a, T value, Comparator<? super T> comparator) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start + (end - start) / 2;
        int cmp = comparator.compare(a[mid], value);
        if (cmp == 0) {
            return mid;
        } else if (cmp > 0) {
            end = mid;
        } else {
            start = mid + 1;
        }
    } while (start < end);
    return -1;
}

内容的提问来源于stack exchange，提问作者douglasdotv