java - 为什么二分查找返回-1

Question

我正在开发一个小程序:

public static void main( String args[])
    {
        String[] places = {"Bangalore","Pune","San Francisco","New York City"};
        Arrays.sort(places, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.compareTo(o1);
        }
    });
        System.out.println(Arrays.binarySearch(places, "New York City"));
    }

这个程序正在打印 -1，但我的数组中有“纽约市”，那么为什么在这种情况下结果为负数？

Answer 1

通常，Arrays.binarySearch 假定数组中的项目已按其自然顺序排序。如果不按这种方式排序，二分搜索算法将不起作用。

您的比较器正在按照与自然顺序相反的顺序进行排序，因此算法无法找到纽约市。

但是有一个 overload of binarySearch that takes a Comparator ，以便算法可以假设它的排序方式与Comparator定义顺序相同。

The array must be sorted into ascending order according to the specified comparator (as by the sort(T[], Comparator) method) prior to making this call.

在 binarySearch 调用中重用您的Comparator。

String[] places = {"Bangalore","Pune","San Francisco","New York City"};

Comparator<String> c = new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
};
Arrays.sort(places, c);
System.out.println(Arrays.binarySearch(places, "New York City", c));

然后您将得到 2 的正确输出。