使用`Collections.BinarySearch`签名实现二分搜索

Question

static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

public class BinarySearch {
    public static <Q extends Comparable<? super T>, T>
    int search(List<Q> xs, T x) {
        return search(xs, x, Q::compareTo);
    }

    public static <T>
    int search(List<? extends T> xs, T x, Comparator<? super T> cmp) {
        int l = 0, r = xs.size() - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (cmp.compare(xs.get(mid), x) == 0)
                return mid;

            if (cmp.compare(xs.get(mid), x) < 0)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return xs.size();
    }
}

PS：如果您想知道为什么集合中的签名看起来像它们的样子，这里有一个解释：集合的这两个通用签名有何不同。BinarySearch？

PPS：曾经有一个答案（现在删除了），您不能在需要比较器的地方传递t::compareto。好吧，我相信您可以，下面是我的QuickSort的工作实现，它可以做到这一点:https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/QuickSort.java

Answer 1

其实我不明白为什么要用Q：

public static <T extends Comparable<T>>
int search(List<? extends T> xs, T x) {
    return search(xs, x, T::compareTo);
}

对我来说会编译和看起来足够了。它允许我同时做两件事：

BinarySearch.search(new ArrayList<Timestamp>(), new Date());
BinarySearch.search(new ArrayList<Date>(), new Timestamp(0L));

这里非常重要的一点是，这实际上意味着（或多或少）：

int search(List<? extends T> xs, final T x) {
    return search(xs, x, new Comparator<T>() {
      @Override
      public int compare(T o1, T o2) {
        return x.compareTo(o2);
      }
    });
}