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;
        }
}

wordIndex*-1 is a long way of writing -wordIndex

Sergey Kalinichenko
– Sergey Kalinichenko

2014-04-03 15:32:51 +00:00
Commented Apr 3, 2014 at 15:32 — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Apr 3, 2014 at 15:32
Someone didn't do their homework... APCS?

Anubian Noob
– Anubian Noob

2014-04-03 15:33:16 +00:00
Commented Apr 3, 2014 at 15:33 — Anubian Noob
– Anubian Noob, Commented Apr 3, 2014 at 15:33
Could you please elaborate?

user2904796
– user2904796

2014-04-03 15:37:34 +00:00
Commented Apr 3, 2014 at 15:37 — user2904796
– user2904796, Commented Apr 3, 2014 at 15:37

Sergey Kalinichenko · Accepted Answer · 2014-04-03 15:39:49Z

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.

answered Apr 3, 2014 at 15:39

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java Prefix Search with binary search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related