Java：在排序列表中查找元素的最佳方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/658364/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: What is the best way to find elements in a sorted List?
提问by Jake
I have a
我有一个
List<Cat>
sorted by the cats' birthdays. Is there an efficient Java Collections way of finding all the catsthat were born on January 24th, 1983? Or, what is a good approach in general?
按猫的生日排序。是否有一种高效的 Java Collections 方法可以找到所有出生于 1983 年 1 月 24 日的猫？或者，一般来说什么是好的方法？
回答by Michael Myers
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.
如果列表很长和/或没有多少猫共享一个生日，这应该是对直接迭代的重大胜利。
Here's the sort of code I'm thinking of. Note that I'm assuming a random-accesslist; for a linked list, you're pretty much stuck with iteration. (Thanks to fred-o for pointing this out in the comments.)
这是我正在考虑的代码类型。请注意，我假设有一个随机访问列表；对于链表，您几乎无法使用迭代。（感谢 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;
回答by Mehrdad Afshari
Binary search is the classic way to go.
二分查找是经典的方法。
Clarification: I said you use binary search. Not a single method specifically. The algorithm is:
澄清：我说你使用二分查找。没有一个具体的方法。算法是：
//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 ];
回答by basszero
Google Collectionscan do what you want by using a Predicate and creating a filtered collection where the predicate matches dates.
Google Collections可以通过使用谓词并创建谓词匹配日期的过滤集合来执行您想要的操作。
回答by siddhadev
If you need a really fast search use a HashMap with the birthday as a key. If you need to have the keys sorted use a TreeMap.
如果您需要真正快速的搜索，请使用以生日为键的 HashMap。如果您需要对键进行排序，请使用 TreeMap。
Because you want to allow multiple cats to have the same birthday, you need to use a Collection as a value in the Hast/TreeMap, e.g.
因为要让多只猫的生日相同，所以需要在Hast/TreeMap中使用一个Collection作为值，例如
Map<Date,Collection<Cat>>
回答by Nuno Furtado
Unless you somehow indexed the collection by date, the only way would be to iterate over all of them
除非您以某种方式按日期索引集合，否则唯一的方法是迭代所有这些
