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?

Asked by: Lydia870 | Posted: 23-01-2022

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

Answered by: Kelvin965 | Posted: 24-02-2022

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

Answered by: Oliver99 | Posted: 24-02-2022

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

Answered by: Fenton823 | Posted: 24-02-2022

Answer 4

Although the answer from Keeg is valid in 1.6 in 1.5 there is no method lower() (We're unfortunate to develop against 1.5 :-( )

this one works in 1.5

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
import java.util.TreeSet;

public class GetNearestDate {

  public static void main( String[] args ) throws ParseException {

    final SimpleDateFormat simpleDateFormat = new SimpleDateFormat( "dd.MM.yyyy HH:mm:ss" );

    List< Date > otherDates = Arrays.asList( new Date[]{
      simpleDateFormat.parse( "01.01.2008 01:00:00" ) ,
      simpleDateFormat.parse( "01.01.2008 01:00:02" ) } );
    System.out.println( simpleDateFormat.parse( "01.01.2008 01:00:00" ).equals(
      get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:01" ) ) ) );
    System.out.println( simpleDateFormat.parse( "01.01.2008 01:00:02" ).equals(
      get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:03" ) ) ) );
    System.out.println( null == get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:00" ) ) );
  }

  public static Date get( List< Date > otherDates , Date dateToApproach ) {
    final TreeSet< Date > set = new TreeSet< Date >( otherDates );
    set.add( dateToApproach );
    final ArrayList< Date > list = new ArrayList< Date >( set );
    final int indexOf = list.indexOf( dateToApproach );
    if ( indexOf == 0 )
      return null;
    return list.get( indexOf - 1 );
  }

}

Answered by: Lydia940 | Posted: 24-02-2022

Answer 5

`NavigableSet::lower`

The Answer by Keeg is cleverly brief. The idea there is to make use of the lower method defined in the NavigableSet interface and implemented in the TreeSet class.

But like the other answers it uses the old outmoded date-time classes bundled with the earliest versions of Java. Below is an updated version using java.time classes.

The old question and answers are using either java.util.Date which is a moment on the timeline in UTC representing both a date and a time-of-day, or the java.sql.Date which awkwardly extends util.Date while pretending it does not have a time-of-day. A confusing mess.

java.time

Those troublesome old classes have been supplanted by the java.time classes built into Java 8 and later. See Oracle Tutorial. Much of the functionality has been back-ported to Java 6 & 7 in ThreeTen-Backport and further adapted to Android in ThreeTenABP.

`LocalDate`

The LocalDate class represents a date-only value without time-of-day and without time zone. While these objects store no time zone, note that time zone (ZoneId) is crucial in determining the current date. For any given moment the date varies around the globe by time zone.

ZoneId zoneId = ZoneId.of( "America/Montreal" );
LocalDate today = LocalDate.now( zoneId );  // 2016-06-25

ISO 8601

Tip: Pad those month and day-of-month numbers with a leading zero. This makes them comply with the ISO 8601 standard date-time formats. These formats are used by default in java.time when parsing/generating strings that represent date-time values.

So use 2008-10-01 rather than 2008-10-1. If padding is not feasible, parse using DateTimeFormatter.

NavigableSet dates = new TreeSet( 3 );
dates.add( LocalDate.parse( "2008-10-01" );
dates.add( LocalDate.parse( "2008-10-02" );
dates.add( LocalDate.parse( "2008-10-04" );
LocalDate target = LocalDate.parse( "2008-10-03" );
LocalDate hit = dates.lower( target );
// Reminder: test for `null == hit` to see if anything found.

Answered by: Kirsten339 | Posted: 24-02-2022

Answer 6

Have you looked at the JodaTime API? I seem to recall a feature like this being available.

Answered by: Joyce157 | Posted: 24-02-2022

Still can't find your answer? Check out these amazing Java communities for help...

top