为什么二进制搜索返回 -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>() {&nbsp; &nbsp; @Override&nbsp; &nbsp; public int compare(String o1, String o2) {&nbsp; &nbsp; &nbsp; &nbsp; return o2.compareTo(o1);&nbsp; &nbsp; }};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) {&nbsp; &nbsp; &nbsp;return o1.compareTo(o2);}因此，如果您按升序对其进行排序，它将起作用