Hello, this is a binary seacrh algorithm im using to find if a prefix of a word
ID: 672857 • Letter: H
Question
Hello, this is a binary seacrh algorithm im using to find if a prefix of a word exists in a dictionary --an arraylist of words of all different types and lengths given by my instructor. It throws and exception when the peefix is longer than the word (.subString) but when i tried to fix this with if statements, it started to produce inccorect results. What should i do?
public int searchPrefix(String prefixKey, int minIndex, int maxIndex){
if(minIndex>maxIndex){
return-1;
}
int midIndex=(maxIndex-minIndex)/2+minIndex;
if(newDictionary.get(midIndex).substring(0,prefixKey.length()).compareTo(prefixKey)>0){
return searchPrefix(prefixKey,minIndex,maxIndex-1);
}
else if(newDictionary.get(midIndex).substring(0,prefixKey.length()).compareTo(prefixKey)<0){
return searchPrefix( prefixKey, midIndex+1,maxIndex);
}
else {
return midIndex;
}
}
Explanation / Answer
Have taken the binarySearch method from Collections class and modified as per your need.
Hope this will help you.
private static int binarySearch(List<String> list, String key)
{
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
String midVal = list.get(mid);
int cmp = -1;
if (midVal.length() > key.length())
cmp = midVal.substring(0, key.length()).compareTo(key);
else
cmp = key.substring(0, midVal.length()).compareTo(midVal) * -1;
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -1; // key not found
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.