Java Prefix Search with binary search

Question

I have been trying to search for a specific string within an array of words (a lexicon) using java's binary search method and then determine whether the string is a word, prefix, or not a word. If the index returned is greater than or equal to zero, the string is a word. If the index returned is less than zero, then I have to determine whether it is not a word, or a prefix.

For instance, For example,when looking up “ela” the value returnedmight be -137. This means that “ela” is not in the lexicon, but if it were to be inserted it would be at index 136. This also means that if the word at index 136 does not begin with “ela” then no word in the lexicon has a prefix of “ela”. So, any non-negative value returned by binarySearch means the status of a word is LexStatus.WORD. If the value returned is negative, one call of the appropriate String.startsWith() method can determine if LexStatus.PREFIX should be returned (make sure you don’t go off the end of the array of words in the lexicon when calling startsWith).

The code I have written so far looks like this. I pass the J-units tests for .isWord() and .isNotWord(); however I am failing the .isPrefix() tests, where I am currently labeling the prefixes as non-words. Can you guys please help me spot my error?

    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

You are computing the checkIndex incorrectly.

From the documentation of binarySearch you know that wordIndex = (-(insertion point) - 1). Therefore wordIndex+1 = -(insertion point), so after flipping the sign upi get -(wordIndex+1) = insertion point

int checkIndex = -(wordIndex+1);

Your code does the negation and addition in reverse order, so your code checks a wrong word.

Note: the word that you see at checkIndex is the word that follows, not precedes, s in lexicographic order. Therefore, you should rename precedingWord variable to nextWord.