Sietse Sietse - 5 months ago 9
Java Question

Best way to find date nearest to target in a list of dates?

I have a list of Date objects, and a target Date. I want to find the date in the list that's nearest to the target date, but only dates that are before the target date.

Example:
2008-10-1
2008-10-2
2008-10-4

With a target date of 2008-10-3, I want to get 2008-10-2

What is the best way to do it?

Answer

Sietse de Kaper solution assumes a reverse sorted list, definitely not the most natural thing to have around

The natural sort order in java is following the ascending natural ordering. (see Collection.sort http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List) documentation)

From your example,

target date = 2008-10-03 
list = 2008-10-01 2008-10-02 2008-10-04 

If another developper uses your method with a naive approach he would get 2008-10-01 which is not what was expected

  • Don't make assumptions as to the ordering of the list.
  • If you have to for performance reasons try to follow the most natural convention (sorted ascending)
  • If you really have to follow another convention you really should document the hell out of it.

    private Date getDateNearest(List<Date> dates, Date targetDate){
      Date returnDate = targetDate
      for (Date date : dates) {
        // if the current iteration'sdate is "before" the target date
        if (date.compareTo(targetDate) <= 0) {
          // if the current iteration's date is "after" the current return date
          if (date.compareTo(returnDate) > 0){
            returnDate=date;
          }
        }
      }  
      return returnDate;
    }
    

    edit - I also like the Treeset answer but I think it might be slightly slower as it is equivalent to sorting the data then looking it up => nlog(n) for sorting and then the documentation implies it is log(n) for access so that would be nlog(n)+log(n) vs n