How do I sort an array of string for binary search. Below I always recieve a minus number for my index instead of the correct index. Please help? If the word is not in the array -1 should be returned.
public static int binary (String [] theword, String a) {
int index = -1;
Arrays.sort(theword);
Arrays.toString(theword);
index = Arrays.binarySearch(theword, a);
return index;
}
It works, see below
public static void main(String... args) {
String words[] = { "abc3", "abc2", "abc1", "abc4" };
Arrays.sort(words);
System.out.println(Arrays.toString(words));
{
String word = "abc3";
int index = Arrays.binarySearch(words, word);
index = index >= 0 ? index : -1;
System.out.println(word + " = " + index);
}
{
String word = "abc11";
int index = Arrays.binarySearch(words, word);
index = index >= 0 ? index : -1;
System.out.println(word + " = " + index);
}
}
Output
[abc1, abc2, abc3, abc4]
abc3 = 2
abc11 = -1
You return the index from the sorted array while you need an index from the original array.
The documentation states that the return value for Arrays.binarySearch() is as follows:
Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
So clearly your word "to" was not found by binary search. Moreover, had it existed, it would have been in the 10th index of this array. As -(10) -1 == -11
There is a good possibility that you are searching for the word to however the data in the array contains the word to with some spaces around it giving you the undesired, yet correct, result of binary search.
A common mistake that I have seen is a space being added to the word in question. Apply the trim() function on each word before adding to your array.
to? I doubt it would if the java official binary search method can't find it. You only need to trim things once. Trimming before putting into the array is all you need to do.
a, and then post the output here