Java: What is the best way to find items in a sorted list?

Question

I have

List<Cat> 

sorted by cats birthdays. Is there an effective way for Java Collections to find all cats born on January 24, 1983? Or, what is a good approach overall?

Answer 1

Collections.binarySearch() .

Assuming cats are sorted by birthday, this will give the index of one of the cats with the correct birthday. From there, you can iterate back and forth until you click on another birthday.

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

Here is the code I'm thinking of. Please note that I assume random access ; for a linked list, you are heavily obsessed with iterating. (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 that you are using binary search. This is not the only method. Algorithm:

 //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 Predicate and creating a filtered collection where the predicate matches dates.

Answer 4

If you somehow did not index the collection by date, the only way is to iterate over all of them

Answer 5

If you need a really quick search, use Happy Birthday HashMap as the key. If you need to sort keys, use TreeMap.

Since you want to allow several cats to have the same birthday, you need to use Collection as a value in Hast / TreeMap, for example.

  Map<Date,Collection<Cat>>