java - 在 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

您应该使用booleanstartsWith(String prefix)而不是intcompareTo(Strings)。

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

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