为什么二进制搜索返回 -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，但我的数组中有 "New York City" 那么为什么在这种情况下结果为负数？

Answer 1

比较器正在按相反的字母顺序排序。二进制搜索需要数组按升序排序。

你的比较器的顺序是错误的。尝试：

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

Answer 2

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

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

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

Answer 3

Arrays.binarySearch 需要数组按升序顺序排序，但在你的情况下你正在制作它 descending。如果你用下面的方法改变你的比较函数，它将按ascending order

排序

public int compare(String o1, String o2) {
     return o1.compareTo(o2);
}

因此，如果您按升序排序，它将起作用

Answer 4

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

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

但是有一个 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 的正确输出。

Answer 5

如果您使用的是 IDE，请在 Arrays.binarySearch 方法中放置一个断点。您的数组以

开头

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

但排序后变成：

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

因此，当您使用二分查找时，它首先查看 "Pune"，然后查看 "San Francisco"，因为二分查找的性质只查找 "tree" 的一半。就像其他人所说的那样，尝试更改比较器的顺序，或尝试其他搜索算法。

为什么二进制搜索返回 -1

Why binary search is returning -1

java

sorting

binary-search