user655321 user655321 - 7 months ago 115
Java Question

Using binary search in ArrayList to find a word with a given prefix

I am working on implementing a binary search algorithm to find a word that contains the prefix argument. This is what I have at the moment but the output isn't correct.

public static int myBinarySearch2(List<String> arrayList, String prefix) {
int first = 0;
int last = arrayList.size() - 1;
int mid = 0;

while (first <= last) {
mid = (first + last) / 2;
int c = prefix.compareTo(arrayList.get(mid));
if (c > 0) {
first = mid + 1;
} else if (c == 0) {
return mid;
} else
last = mid - 1;
}
return mid;
}


If anyone can look at my code and provide me so feedback, id appreciate it. Thanks!

Answer

You should use boolean startsWith(String prefix) instead of int compareTo(String s).

The last one compares strings char by char fully, it isn't what you are expecting.

String s = arrayList.get(mid);
int c = s.startsWith(prefix) ? 0 : prefix.compareTo(s);
Comments