为什么二进制搜索返回 -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假设数组中的项目已按其自然顺序排序。如果不以这种方式排序，则二分搜索算法将不起作用。

您Comparator正在按自然顺序的相反顺序排序，因此算法找不到纽约市。

但是它的重载binarySearch需要 aComparator，因此算法可以假设它的排序方式与Comparator定义顺序的方式相同。

数组必须根据指定的比较器按升序排序（如sort(T[], Comparator) method)在进行此调用之前。

Comparator在您的binarySearch通话中重用您的。

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。

Answer 2

使用二分搜索时，被搜索的数据对象数组必须根据用于搜索的比较器排序。

在您的示例中，城市没有任何特定顺序，因此搜索将不起作用。

您的比较器按逆字母顺序排序，因此数组也必须按逆字母顺序排列。

Answer 3

Arrays.binarySearch需要数组按升序排序，但在您的情况下，您将其降序。如果您使用下面的更改比较函数，它将按升序排序

public int compare(String o1, String o2) {

     return o1.compareTo(o2);

}

因此，如果您按升序对其进行排序，它将起作用