为什么 Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 方法需要 Comparator 对象作为参数？

Question

这是我的代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class MyComp implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
    
}
public class CollectionsAlgo2 {

    public static void main(String[] args) {
        // Create an ArrayList
        ArrayList<String> al = new ArrayList<>();
        
        // Add elements to the array list.
        al.add("C");
        al.add("A");
        al.add("E");
        al.add("B");
        al.add("D");
        al.add("F");
        al.add(1, "A2");
        
        System.out.println("al: "+al);
        Collections.sort(al);
        System.out.println("al after sorting: "+al);
        int pos = Collections.binarySearch(al, "B", new MyComp());
        System.out.println("pos: "+pos);

    }

}

我的问题是在 Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 中使用 Comparator 引用作为参数的目的是什么，因为我们已经传递了按升序排序的列表？

这个比较器参考如何帮助进行二分搜索？

Answer 1

从根本上来说，二分搜索算法需要知道如何比较元素。当它检查二分点时，它需要知道您正在搜索的元素是在左边还是在右边。这就需要对比了。

\n

Collections有两种binarySearch方法，一种带比较器，一种不带。如果您的元素是，Comparable那么您不需要传递比较器。您只需传递列表和搜索键即可：

\n

int binarySearch\xe2\x80\x8b(List<? extends Comparable<? super T>> list, T key)\n

\n

如果不是，Comparable那么您需要告诉binarySearch如何通过传递自定义来比较它们Comparator：

\n

int binarySearch\xe2\x80\x8b(List<? extends T> list, T key, Comparator<? super T> c)\n

\n

在您的示例代码中，Strings 是Comparable，所以您不需要MyComp.

\n

int pos = Collections.binarySearch(al, "B");\n

\n