Java: What is the best way to find elements in a sorted List?

Question

I have a

List<Cat>

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?

Answer 1

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.

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;

Answer 2

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 ];

Answer 3

Google Collections can do what you want by using a Predicate and creating a filtered collection where the predicate matches dates.

Answer 4

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.

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.

      Map<Date,Collection<Cat>>

Answer 5

Unless you somehow indexed the collection by date, the only way would be to iterate over all of them