java - 仅使用 .get() 和 .size() 计算有序 ArrayList 中的部分匹配项

Question

这里的代码返回列表(排序的自定义数组列表)中具有指定前缀和后缀的元素数。它有效，但它应该花费 log(n) + k，其中 k 是列表中具有该前缀的字符串数。无论如何让它更高效和更快？

//StringList,custom ArrayList only contains size() and get()
public int countMatches(StringList a, String prefix, String suffix) {

    int count = 0;

    for (int i = 0; i < a.size(); i++) {
        String temp = a.get(i);
        if (temp.startsWith(prefix) && temp.endsWith(suffix)) {
            count++;
        }
    }
    return count;
}

更新: 这是二分搜索找到第一个前缀后的代码，该代码应该去掉没有前缀的单词。但是它不起作用，怎么回事？

        for (int i = low; i < high; i++) {

          if (!(prefix.compareTo(a.get(i)) > 0)) {
               high = i;
               break;
          }
        }

Answer 1

如果列表已排序，您可以执行 binary search查找以前缀开头的第一个字符串。