首页 文章

Java前缀使用二进制搜索进行搜索

提问于
浏览 次
1

我一直在尝试使用java的二进制搜索方法在一个单词数组（一个词典）中搜索一个特定的字符串，然后确定该字符串是单词，前缀还是单词 . 如果返回的索引大于或等于零，则该字符串为单词 . 如果返回的索引小于零，那么我必须确定它不是单词还是前缀 .

例如，例如，当查找“ela”时，返回的值可能是-137 . 这意味着“ela”不在词典中，但是如果它被插入则它将在索引136处 . 这也意味着如果索引136处的单词不以“ela”开头，那么词典中没有单词前缀“ela” . 因此，binarySearch返回的任何非负值意味着单词的状态为LexStatus.WORD . 如果返回的值是负数，则调用相应的String.startsWith（）方法可以确定是否应该返回LexStatus.PREFIX（确保在调用startsWith时不会在词典中的单词数组的末尾） .

到目前为止我写的代码看起来像这样 . 我通过.isWord（）和.isNotWord（）的J单元测试;但我没有通过.isPrefix（）测试，我目前将前缀标记为非单词 . 你能帮我看看我的错误吗？

public LexStatus wordStatus(String s) {
    String [] myWordsArray = new String[myWords.size()];
    myWords.toArray(myWordsArray);
    int wordIndex= Arrays.binarySearch(myWordsArray,s);
    if(wordIndex>=0){
        return LexStatus.WORD;
    }
    else{
        int checkIndex = (wordIndex*-1)+1;
        if(checkIndex<=myWords.size()-1){
            String precedingWord= myWords.get(checkIndex);
            String check1=precedingWord.toLowerCase();
            String check2= s.toLowerCase();
            if(check1.startsWith(check2)){
                return LexStatus.PREFIX;
            }
            return LexStatus.NOT_WORD;
        }
        return LexStatus.NOT_WORD;
        }
}
java binary-search

1 回答

  • 1

    您正在错误地计算 checkIndex .

    从 binarySearch 的文档中你知道 wordIndex = (-(insertion point) - 1) . 因此 wordIndex+1 = -(insertion point) ，所以在翻完标志之后得到 -(wordIndex+1) = insertion point

    int checkIndex = -(wordIndex+1);

    您的代码以相反的顺序执行否定和添加，因此您的代码会检查错误的单词 .

    注意：您在 checkIndex 中看到的单词是按字典顺序排列的单词，而不是 s . 因此，您应该将 precedingWord 变量重命名为 nextWord .

    回复于

相关问题