Java：在排序列表中查找元素的最好方法是什么？ [英] Java: What is the best way to find elements in a sorted List?

问题描述

我有一个

List<Cat>

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

sorted by the cats' birthdays. Is there an efficient Java Collections way of finding all the cats that were born on January 24th, 1983? Or, what is a good approach in general?

推荐答案

Collections.binarySearch（） 。

假设猫按生日排序，这将给出一只猫正确生日的索引。

Assuming the cats are sorted by birthday, this will give the index of one of the cats with the correct birthday. From there, you can iterate backwards and forwards until you hit one with a different birthday.

如果列表很长和/或不是很多猫共享一个生日，这应该在直接迭代中是一个重大的胜利。

If the list is long and/or not many cats share a birthday, this should be a significant win over straight iteration.

这是我正在想的那种代码。请注意，我假设随机访问 a> list;对于链表，你几乎停留在迭代。 （感谢fred-o在评论中指出这一点。）

Here's the sort of code I'm thinking of. Note that I'm assuming a random-access list; for a linked list, you're pretty much stuck with iteration. (Thanks to fred-o for pointing this out in the comments.)

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;

这篇关于Java：在排序列表中查找元素的最好方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！