代码之家 › 专栏 › 技术社区 › learner

为什么二进制搜索返回-1[重复]

binary-search sorting java

2

learner · 技术社区 · 7 年前

我正在做一个小程序:

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"));
    }

5 回复 | 直到 7 年前

1

4

rgettman 7 年前

正常情况下, Arrays.binarySearch 假设数组中的项已按其自然顺序排序。如果不按这种方式排序,二进制搜索算法就不起作用。

Comparator 排序的顺序与自然顺序相反,因此算法无法找到纽约市。

但是有一个 overload of binarySearch that takes a Comparator ,这样算法就可以假设它的排序方式与 比较器 定义顺序。

sort(T[], Comparator) method) 在打这个电话之前。

重用您的 比较器 在你的打电话。

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 .

2

1

Jim Garrison 7 年前

你的比较仪排序颠倒按字母顺序排列,因此数组也必须按逆字母顺序排列。

3

0

kaushik 7 年前

数组.二进制搜索 需要排序数组提升命令,但在你的情况下,你是使它降序提升秩序

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

提升

4

0

user10419532 user10419532 7 年前

如果您使用的是IDE,请在Arrays.binarySearch方法中放置断点。你的阵法开始于

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

但经过分类后会变成:

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

所以当你使用二进制搜索时,它首先看“Pune”,然后看“San Francisco”,因为二进制搜索的本质是只看“树”的一半。正如其他人所说,尝试更改比较器的顺序,或者尝试其他搜索算法。

5

0

andreybleme 7 年前

你的比较仪顺序不对。尝试:

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"));