1

如何对字符串数组进行排序以进行二进制搜索。下面我总是收到一个负数作为我的索引而不是正确的索引。请帮忙？如果单词不在数组中，则应返回 -1。

  public static int binary (String [] theword, String a) {
    int index = -1;
        Arrays.sort(theword);
        Arrays.toString(theword);
        index = Arrays.binarySearch(theword, a);
    return index;

}
4

3 回答 3

3

有效，见下文

public static void main(String... args) {

    String words[] = { "abc3", "abc2", "abc1", "abc4" };

    Arrays.sort(words);
    System.out.println(Arrays.toString(words));
    {
        String word = "abc3";
        int index = Arrays.binarySearch(words, word);
        index = index >= 0 ? index : -1;
        System.out.println(word + " = " + index);
    }
    {
        String word = "abc11";
        int index = Arrays.binarySearch(words, word);
        index = index >= 0 ? index : -1;
        System.out.println(word + " = " + index);
    }
}

输出

[abc1, abc2, abc3, abc4]
abc3 = 2
abc11 = -1

当您需要原始数组中的索引时，您从排序后的数组中返回索引。

于 2013-04-18T16:15:59.807 回答
1

文档指出Arrays.binarySearch()的返回值如下：

返回：
搜索键的索引，如果它包含在数组中；否则，（-（插入点）- 1）。插入点定义为将键插入数组的点：第一个元素的索引大于键，或者如果数组中的所有元素都小于指定的键，则为 a.length。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

很明显，二进制搜索没有找到您的单词“to”。此外，如果它存在，它就会在这个数组的第 10 个索引中。作为-(10) -1 == -11

您很有可能正在搜索该单词to，但数组中的数据包含该单词to，其周围有一些空格，从而为您提供了不希望的但正确的二分搜索结果。

于 2013-04-18T16:22:30.667 回答
1

我看到的一个常见错误是在相关单词中添加了一个空格。在添加到数组之前，对每个单词应用 trim() 函数。

于 2013-04-18T16:26:32.860 回答