使用`Collections.binarySearch`签名实现二分查找

Question

使用`Collections.binarySearch`签名实现二分查找

3

这是我尝试实现二分查找的代码：

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：如果你想知道为什么Collections的签名看起来像这样，这里有一个解释：这两个泛型签名的Collections.binarySearch有何不同？

PPS：曾经有一个（现已删除的）答案，声称你不能将T::compareTo传递到需要Comparator的位置。嗯，我相信你可以，在这里是我实际工作中的QuickSort实现：https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/QuickSort.java

- alisianoi

1

你的二分查找还有问题。如果没有找到元素，它缺少一个return语句。 - Codo

@Codo 谢谢，已修复。泛型怎么样？ - alisianoi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernd Ebertz · Accepted Answer

实际上我不明白为什么要使用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);
      }
    });
}

现在我们可以清楚地看到：x需要是Comparable类型。这在你的方法中没有说明。相反，定义了类型Q，但实际上没有参与者属于此类型。因此，比较器不是严格兼容的，但它必须是这样的，因为x的compareTo方法是比较器的实现。另一种方法是使用Comparator.naturalOrder()，但仍然需要将T定义为Comparable类型。