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

我有一个

List

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

Collections.binarySearch().

假设猫按生日分类,这将给出其中一只猫的生日正确指数.从那里开始,你可以向前和向后迭代,直到你遇到一个生日不同的人.

如果列表很长和/或没有多少猫共享生日,这应该是直接迭代的重大胜利.

这是我正在考虑的那种代码.请注意,我假设一个随机访问列表; 对于链表,你几乎坚持迭代.(感谢fred-o在评论中指出这一点.)

List cats = ...; // sorted by birthday
List catsWithSameBirthday = new ArrayList();
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;

二进制搜索是经典的方法.

澄清:我说过你使用二进制搜索.没有一个具体的方法.算法是:

//pseudocode:

index = binarySearchToFindTheIndex(date);
if (index < 0) 
  // not found

start = index;
for (; start >= 0 && cats[start].date == date; --start);
end = index;
for (; end < cats.length && cats[end].date == date; ++end);

return cats[ start .. end ];