使用`Collections.binarySearch`签名实现二进制搜索 [英] Implement binary search using the `Collections.binarySearch` signature

问题描述

这是我在尝试执行必须遵循的二进制搜索的尝试：

  static< T> int binarySearch（List扩展了Comparable超级T列表，T键）
 static< T> int binarySearch（List 但是，我想避免代码重复，而是将一种实现委托给另一种实现（当前，将第一种实现委托给第二种实现）。为此，我需要摆脱通配符？并使用第二个通用类型，如下所示：
 公共类BinarySearch {
公共静态< Q扩展了Comparable< ;?超级T>，T> 
 int search（List Q Qs，T x）{
 return search（xs，x，Q :: compareTo）; 
} 
 
公共静态< T> 
 int search（List <？extends T> xs，Tx，Comparator <？super T> cmp）{
 int l = 0，r = xs.size（）-1; 
 
而（l <= r）{
 int mid = l +（r-l）/ 2; 
 
 if（cmp.compare（xs.get（mid），x）== 0）
返回中点; 
 
如果（cmp.compare（xs.get（mid），x）< 0）
 r =中-1; 
 else 
 l =中+ 1； 
} 
 
 return xs.size（）; 
} 
} 
  
不幸的是，这无法编译，并因错误而失败：
 
 
 
 不能从静态上下文中引用非静态方法 
 
 
 
我该如何解决？
 
 
 
  PS：如果您想知道为什么 Collections 看他们做事的方式，这里有一个解释： Collections.binarySearch的这两个通用签名有何不同？  
 
 
 
  PPS：曾经（现在已删除）答案是您不能在期望比较器的地方传递 T :: compareTo 。好吧，我相信您可以，这是我正在执行的QuickSort实现，它确实做到了： https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/ QuickSort.java   
解决方案
实际上我不明白为什么要使用Q：
 公共静态< T扩展Comparable< T> 
 int search（List<？extended 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搜索（List< ;?扩展T> xs，最终T x）{
返回搜索（xs，x，新Comparator  ;（）{
 @Override 
 public int compare（T o1，T o2）{
 return x.compareTo（o2）; 
} 
}）; 
} 
  
现在我们清楚地看到：x需要为可比较类型。您的方法没有说明。取而代之的是定义了类型Q，但实际上没有参与者是这种类型的。因此，比较器并非严格兼容，但必须兼容，因为x的compareTo方法是比较器的实现。顺便说一句，另一种方法是使用 Comparator.naturalOrder（）作为技巧，但仍必须将T定义为可比较的。
 
Here is my attempt at implementing the binary search that must follow:
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)
However, I would like to avoid code duplication and delegate one of the implementations to the other (currently, the first to the second). To do that I need to get rid of the wildcard ? and use a second generic type like so:
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();
    }
}
Unfortunately, this does not compile, failing with the error:

Non-static method cannot be referenced from a static context

How could I fix that?

PS: if you wonder why the signatures from Collections look the way they do, here is an explanation: How do these two generic signatures for Collections.binarySearch differ?

PPS: there used to be (a now deleted) answer that you cannot pass T::compareTo in place where a Comparator is expected. Well, I believe that you can, here is my working implementation of QuickSort that does exactly that: https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/QuickSort.java
解决方案
Actually I don't understand why use Q:
public static <T extends Comparable<T>>
int search(List<? extends T> xs, T x) {
    return search(xs, x, T::compareTo);
}
will compile and looks sufficient to me.
It allows me to do both:
BinarySearch.search(new ArrayList<Timestamp>(), new Date());
BinarySearch.search(new ArrayList<Date>(), new Timestamp(0L));
A very important point here is that this actually means (more or less):
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);
      }
    });
}
Now we clearly can see: x needs to be of type Comparable. This wasn't stated in your approach. Instead there was a type Q defined, but no participant actually was of this type. So the Comparator wasn't strictly compatible, but it has to, as the compareTo-method of x is the implementation of the comparator. BTW another approach is to use Comparator.naturalOrder() for the trick, but still T must be defined to be a Comparable.

                        
这篇关于使用`Collections.binarySearch`签名实现二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！