在 ArrayList 中使用二进制搜索查找具有给定前缀的单词

Question

我正在研究实现一个二进制搜索算法来查找包含前缀参数的单词。这就是我目前所拥有的，但输出不正确。

    public static int myBinarySearch2(List<String> arrayList, String prefix) {
    int first = 0;
    int last = arrayList.size() - 1;
    int mid = 0;

    while (first <= last) {
        mid = (first + last) / 2;
        int c = prefix.compareTo(arrayList.get(mid));
        if (c > 0) {
            first = mid + 1;
        } else if (c == 0) {
            return mid;
        } else
            last = mid - 1;
    }
    return mid;
}

如果有人可以查看我的代码并向我提供反馈，我将不胜感激。谢谢！

Answer 1

您不应该使用 compareTo 方法来检查单词包含。

比较方法： http://www.tutorialspoint.com/java/java_string_compareto.htm

您可能想使用 .contains 方法： http://www.tutorialspoint.com/java/lang/string_contains.htm

Answer 2

您应该使用 boolean startsWith(String prefix) 而不是 int compareTo(String s)。

最后一个将字符串 char 与 char 进行了完全比较，这不是您所期望的。

String s = arrayList.get(mid);
int c = s.startsWith(prefix) ? 0 : prefix.compareTo(s);

Answer 3

首先记住arrayList需要排序才能使用二分查找，否则他们的return是undefined。我认为这是你的问题。

在 ArrayList 中使用二进制搜索查找具有给定前缀的单词

Using binary search in ArrayList to find a word with a given prefix

java

string

compare

arraylist

binary-search