时间戳

首页 > 解决方案 > 当单词不存在时，递归二进制搜索返回 stackoverflow 错误

java - 当单词不存在时，递归二进制搜索返回 stackoverflow 错误

问题描述

我写了一个递归二进制搜索方法，如果字典中存在这个词，它就可以工作，但是，当我输入一个不存在的词时，比如“rwetjia”，我得到一个stackoverflow错误

    public boolean wordCheck(String target, int start, int end) {
    target.toLowerCase();
    if (end >= 1) {
        int middle = start + (end - start) / 2;
        int targetside = target.compareTo(words.get(middle));// Finds which side the word is on
        if (targetside == 0) {
            return true;
        } // Word is at the middle (the word exists and has been found)
        else if (targetside > 0) {
            return wordCheck(target, middle + 1, end);
        } // If target word is on the right side of the array, "cuts" the other half off
        else {
            return wordCheck(target, start, middle - 1);
        }
    } // If target word is on the left side of the array, "cuts" the other half off
        return false; // Word is not in the dictionary
}

标签： javabinary-search

解决方案

尝试：

if (end >= start) {

代替

if (end >= 1) {

更新：

我假设这end是要考虑的最后一个元素的索引（请参阅我上面的评论）；否则，测试将是：

if (end > start) {

你需要更换：

        return wordCheck(target, start, middle - 1);

和：

        return wordCheck(target, start, middle);

推荐阅读