Java 前缀搜索与二分搜索

Question

我一直在尝试使用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;
        }
}

Answer 1

您错误地计算了 checkIndex。

从binarySearch的文档中您知道wordIndex = (-(插入点) - 1)。因此 wordIndex+1 = -(插入点)，因此翻转符号 upi 后得到 -(wordIndex+1) = 插入点

int checkIndex = -(wordIndex+1);

您的代码以相反的顺序进行求反和加法，因此您的代码检查了错误的单词。

注意:您在 checkIndex 中看到的单词是按字典顺序后面的单词，而不是前面、s。因此，您应该将 precedingWord 变量重命名为 nextWord。