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

Question

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 1

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

Answer 2

private Date getDateNearest(List<Date> dates, Date targetDate){
    return new TreeSet<Date>(dates).lower(targetDate);
}

Doesn't require a pre-sorted list, TreeSort fixes that. It'll return null if it can't find one though, so you will have to modify it if that's a problem. Not sure of the efficency either :P

Answer 3

I currently use the following method, but I'm not sure it's the most effective one, because this assumes an already sorted list, and (potentially) iterates over every single date in the list.

private Date getDateNearest(List<Date> dates, Date targetDate){
  for (Date date : dates) {
    if (date.compareTo(targetDate) <= 0) return date;
  }

  return targetDate;
}