java - 将 binarySearch 与比较器和正则表达式一起使用

Question

我正在尝试编写一个快速搜索来搜索 List<String>我不想遍历列表并手动检查，而是想使用 binarySearch 来执行此操作，但我不确定该怎么做。

旧方法:

for(String s : list) {
  if(s.startsWith("contact.")
     return true;
}

相反，我想要这样的东西:

Collections.sort(list);
Collections.binarySearch(list, FindContactComparator());

有人可以帮我写这个比较器吗？
有没有比使用 binarySearch 更好的方法来做到这一点？

Answer 1

这应该有效:

        Comparator<String> startsWithComparator = new Comparator<String>() {
            public int compare(String currentItem, String key) {
                if(currentItem.startsWith(key)) {
                    return 0;
                }
                return currentItem.compareTo(key);
            }
        };

int index = Collections.binarySearch(items, "contact.", startsWithComparator);

然而，先排序再二分查找的效率低于单遍迭代。

附录:

虽然上面的答案对你有帮助，但还有另一种方法(灵感来自 Scala、Google Collections):

List<String> items = Arrays.asList("one", "two", "three", "four", "five", "six");
int index = find(items, startsWithPredicate("th"));
System.out.println(index);


public static Predicate<String> startsWithPredicate(final String key) {
    return new Predicate<String>(){
        @Override
        public boolean apply(String item) {
            return item.startsWith(key); 
        }
    };
}

public static <T> int find(Collection<T> items, Predicate<T> predicate) {
    int index = 0;
    for(T item: items) {
        if(predicate.apply(item)) {
            return index;
        }
        index++;
    }
    return -1;
}

interface Predicate<T> {
    boolean apply(T item);
}

这里的问题是 find() 方法与您的“匹配”逻辑无关；它只是找到一个满足谓词的元素。所以你可以传递一个不同的谓词实现，例如。它可以检查 'endsWith' 到 find() 方法，它会返回找到的以特定字符串结尾的项目。此外，find() 方法适用于任何类型的集合；它所需要的只是一个将集合元素类型的元素转换为 boolean 值的谓词。这种围绕一个简单逻辑的多行代码也表明 Java 缺乏对一流功能的支持。