递归二进制搜索 Java

Question

我有一个名为 sArray 的数组列表，其中包含大量正确拼写的单词。我需要向这个递归二进制搜索方法（键）发送一个单词并确定它是否拼写正确。我了解递归二进制搜索的工作原理，但是我不确定如何确定在使用我的关键字搜索 sArray 时是否需要向左或向右移动，因为我正在处理字符串而不是整数。

 public int bSearch(String key, int lowIndex, int highIndex) {

    if (lowIndex > highIndex) {
        System.out.print("The word is incorrect");
        return -1;
    }

    mid = (lowIndex + highIndex) / 2;
    if (sArray.get(mid).equals(key)) {
        return mid;
    } else if (key < sArray.get(mid)) {
        return bSearch(key, lowIndex, mid - 1);
    } else {
        return bSearch(key, mid + 1, highIndex);
    }
}

Answer 1

您可以像比较整数一样轻松地比较字符串：

if (testString.compareTo(key) < 0) {
    ...
} else if (testString.compareTo(key) > 0) {
    ...
} else {
    ...
}

Answer 2

compareTo 方法允许您比较任何实现 Comparable 接口的对象。由于 String class 实现了 Comparable 接口，compareTo 将在您的方法中起作用。

使用 compareTo 时要记住的一个小技巧是将其视为减法：

a.compareTo(b) 将 return -1 如果 a - b 导致否定答案。（订购时 a 在 b 之前）

a.compareTo(b) 将 return 1 如果 a - b 导致肯定答案。（点菜时a在b之后）

如果 a - b 结果为 0，

a.compareTo(b) 将 return 0。（a 和 b 在订购时相同）

所以...

 if (key.compareTo(midValue) < 0) {

      //look to the left of mid
 }...

递归二进制搜索 Java

Recursive Binary Search Java

java

recursion

binary-search-tree