使用二分搜索的Java前缀搜索

Question

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

    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=-(insertion point)，所以翻转符号upi后，得到-(wordindex+1)=insertion point

int checkIndex = -(wordIndex+1);

您的代码以相反的顺序执行否定和加法，因此您的代码检查了一个错误的单词。

注意：您在checkindex中看到的词是按词典顺序排在s后面的词，而不是前面的词。因此，您应该将precingword变量重命名为nextword。