使用递归二进制搜索进行拼写检查 - StackOverflow

Question

我有这种递归二进制搜索拼写检查方法。 sArray 包含英国词典中的单词列表。密钥是您可以发送的任何字词。该方法将采用任何单词（键）并使用递归二进制搜索在字典 (sArray) 中查找它。

我不确定我的递归步骤是否正确，我从中间 add/subtract 1 开始新的 high/low 索引。但是，当我运行程序时，我得到一个堆栈溢出错误，表明我的递归没有停止。下面是错误。

Exception in thread "main" java.lang.WhosebugError
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);
    }
}

Answer 1

} 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);
}

注意 +1 和 -1。搜索范围应该是单调递减的。

Answer 2

调用 bSearch 函数时使用

return bSearch(sArray, key, lowIndex, mid - 1);

和

return bSearch(sArray, key, mid+1, highIndex);

使用递归二进制搜索进行拼写检查 - StackOverflow

Spell Checking With Recursive Binary Search - StackOverflow

java

stack-overflow

recursion

binary-search