我有这种递归二进制搜索拼写检查方法。 sArray 保存英格兰词典中的单词列表。 key 是您可以发送的任何单词。该方法将采用任何单词(键)并使用递归二分搜索在字典(sArray)中查找它。
我不确定我的递归步骤是否正确，我在中间加/减 1 作为新的高/低指数。但是，当我运行该程序时，出现堆栈溢出错误，这表明我的递归没有停止。下面是错误。
Exception in thread "main" java.lang.StackOverflowError
at java.lang.String$CaseInsensitiveComparator.compare(String.java:1173)
at java.lang.String.compareToIgnoreCase(String.java:1226)
at Program2.bSearch(Program2.java:111)
at Program2.bSearch(Program2.java:121)
public int bSearch(ArrayList<String> sArray, String key, int lowIndex, int highIndex) {
if (lowIndex > highIndex) {
System.out.println("The word was not found " + c);
c++;
incorrectWords++;
return -1;
}
mid = (lowIndex + highIndex) / 2;
if (sArray.get(mid).compareToIgnoreCase(key)==0) {
correctWords++;
System.out.println("The word " + sArray.get(mid) + " was found *");
return mid;
} else if (sArray.get(mid).compareTo(key) > 0) {
return bSearch(sArray, key, lowIndex, mid + 1);
} else {
return bSearch(sArray, key, mid - 1, highIndex);
}
}
最佳答案
} else if (sArray.get(mid).compareTo(key) > 0) {
return bSearch(sArray, key, lowIndex, mid + 1);
} else {
return bSearch(sArray, key, mid - 1, highIndex);
}
当找不到 key 时，这会卡住。应该是
} else if (sArray.get(mid).compareTo(key) > 0) {
return bSearch(sArray, key, lowIndex, mid - 1);
} else {
return bSearch(sArray, key, mid + 1, highIndex);
}
注意+1和-1。待搜索的范围应该是单调递减的。
关于java - 使用递归二分搜索进行拼写检查 - Thinbug，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28483762/