binary search in java?

Question

import java.util.Arrays;
public boolean isValidPrefix(String prefixToCheck)
{
if ((java.util.Arrays.binarySearch(dictionary, prefixToCheck))>=0)
{
return true;
}
return false;
}

I’m wondering why the return of this binary search is -65537, I was expecting to be a positive number since the String prefixToCheck test is in the dictionary array I created. the dictionary is like this:
gyve
gyved
gyves
gyving
ha
haaf
haafs
haar
haars
habanera
habaneras
habdalah
habdalahs
haberdasher
haberdasheries
haberdashers


I wonder if that method only works if it needs the whole word to work
if it is just a string "h" will it work? and return a positive number?
i think so, but what do you think?

Any help would be appreciated, thanks.

Answer 1

java.util.Arrays.binarySearch() returns a negative number if the exact complete string you gave it does not occur in the array you gave it. This is explained at http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html#binarySearch(java.lang.Object[],%20java.lang.Object).



If you read that description then you'll see that the negative number indicates the position that the given string would have occupied if you were to insert it into the array. This means that you can use the negative number as the basis for a prefix search but you must first convert it to a positive value by reversing the rule that the function uses to convert the "this is where it would have gone" index into a negative number. After you've done that, you can examine the string at that index to see whether it begins with the string you passed to binarySearch() or not. (Use String.startsWith().) If it does then it's the first string in the array that has the desired prefix, and if it doesn't then no string in the array has the desired prefix.

Answer 2

Java Arrays.binarysearch

Answer 3

The Arrays and Collections classes have a binary search method.