Java:在排序列表中查找元素的最佳方法是什么？

我有一个

List<Cat>

按猫的生日排序。有没有一种有效的Java Collections方法可以找到1983年1月24日出生的所有猫？或者，什么是一般的好方法？

最佳答案

Collections.binarySearch() 。

假设猫是按生日排序的，这将为其中一只生日正确的猫提供索引。从那里，您可以向后和向前迭代，直到打到另一个生日。

如果列表很长，并且/或者没有多少猫分享生日，这应该是直接迭代的重大胜利。

这是我正在考虑的代码。请注意，我假设使用random-access列表；对于链表，您几乎陷入了迭代。 (感谢fred-o在评论中指出这一点。)

List<Cat> cats = ...; // sorted by birthday
List<Cat> catsWithSameBirthday = new ArrayList<Cat>();
Cat key = new Cat();
key.setBirthday(...);
final int index = Collections.binarySearch(cats, key);
if (index < 0)
    return catsWithSameBirthday;
catsWithSameBirthday.add(cats.get(index));
// go backwards
for (int i = index-1; i > 0; i--) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
// go forwards
for (int i = index+1; i < cats.size(); i++) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
return catsWithSameBirthday;