Find closest date in array with JavaScript

Question

I have an array with days in it. Each day is an object, for example:

{day_year: "2012", day_month: "08", day_number: "03", day_name: "mon"}

I have also added a timestamp attribute to each day object, by using:

function convertDays() {
    var max_i = days.length;
    for(var i = 0; i < max_i; i++) {
        var tar_i = days[i];
        tar_i.timestamp = new Date(tar_i.day_year, tar_i.day_month, tar_i.day_number);
    }
}

The days in the array are arbitrary, so there is no real logic to them.

Now I want to find the two closest days to any given date. So if the array with days contains

August 2, 2012
August 4, 2012
August 23, 2012

And I search for August 11, 2012, I want it to return August 4, 2012 and August 23, 2012.

I have tried using an answer from another question, that looks like this:

function findClosest(a, x) {
    var lo, hi;
    for(var i = a.length; i--;) {
        if(a[i] <= x && (lo === undefined || lo < a[i])) lo = a[i];
        if(a[i] >= x && (hi === undefined || hi > a[i])) hi = a[i];
    }
    return [lo, hi];
}

However, this returns unidentified.

What would be the most efficient (least processor/memory intensive way) to achieve this?

Edit: "However, how are those results "strange"? Could you provide an example of your code and data?"

I'm now using the following to generate an array of dates:

var full_day_array = [];
for(var i = 0; i < 10; i++) {
    var d = new Date();
    d.setDate(d.getDate() + i);
    full_day_array.push({day_year: d.getFullYear().toString(), day_month: (d.getMonth() + 1).toString(), day_number: d.getDate().toString()});
}

The strange part is, using the code below, this only works for an array of 10 dates or shorter. Whenever I use an array of 11 or more dates, the results become unexpected.

For instance: using an array of 15 dates, starting on August 6, 2012, to August 21, 2012. If I then call findClosest(full_day_array, new Date("30/07/2012"); you would expect it to return {nextIndex: 0, prevIndex: -1}. However, it returns {nextIndex: 7, prevIndex: -1}. Why?

function findClosest(objects, testDate) {
    var nextDateIndexesByDiff = [],
        prevDateIndexesByDiff = [];

    for(var i = 0; i < objects.length; i++) {
        var thisDateStr = [objects[i].day_month, objects[i].day_number, objects[i].day_year].join('/'),
            thisDate    = new Date(thisDateStr),
            curDiff     = testDate - thisDate;

        curDiff < 0
            ? nextDateIndexesByDiff.push([i, curDiff])
            : prevDateIndexesByDiff.push([i, curDiff]);
    }

    nextDateIndexesByDiff.sort(function(a, b) { return a[1] < b[1]; });
    prevDateIndexesByDiff.sort(function(a, b) { return a[1] > b[1]; });


    var nextIndex;
    var prevIndex;

    if(nextDateIndexesByDiff.length < 1) {
        nextIndex = -1;
    } else {
        nextIndex = nextDateIndexesByDiff[0][0];
    }
    if(prevDateIndexesByDiff.length < 1) {
        prevIndex = -1;
    } else {    
        prevIndex = prevDateIndexesByDiff[0][0];
    }
    return {nextIndex: nextIndex, prevIndex: prevIndex};
}

Why do you have them in that format? Can you change the format to be timestamps so you can parse them to proper date objects more easily? — Esailija
– Esailija, Commented Aug 3, 2012 at 11:58
I could indeed change them to timestamps, for example by looping through the days and adding an attribute 'timestamp' to them: days[i].timestamp = new Date(days[i].day_year, days[i].day_month, days[i].day_number); Would that help? — Rein
– Rein, Commented Aug 3, 2012 at 12:03
If you want to speak about efficiency then you should define how do you suppose to use it. For example it matters whether you need to find one closest date in one set of dates or you will have same set of dates and you will search over them several times. — Snowbear
– Snowbear, Commented Aug 3, 2012 at 12:05
I have up to five sets of days, each containing about 200 days. Then I have up to 100 dates for which I have to find the two closest days. — Rein
– Rein, Commented Aug 3, 2012 at 12:10

Bergi · Accepted Answer · 2012-08-03 13:14:13Z

34

You can easily use the sort function with a custom comparator function:

// assuming you have an array of Date objects - everything else is crap:
var arr = [new Date(2012, 7, 1), new Date(2012, 7, 4), new Date(2012, 7, 5), new Date(2013, 2, 20)];
var diffdate = new Date(2012, 7, 11);

arr.sort(function(a, b) {
    var distancea = Math.abs(diffdate - a);
    var distanceb = Math.abs(diffdate - b);
    return distancea - distanceb; // sort a before b when the distance is smaller
});

// result:
[2012-08-05, 2012-08-04, 2012-08-01, 2013-03-20]

To get only results before or after the diffdate, you can filter the array for that:

var beforedates = arr.filter(function(d) {
    return d - diffdate < 0;
}),
    afterdates = arr.filter(function(d) {
    return d - diffdate > 0;
});

If you have your custom array with the {the_date_object: new Date(...)} objects, you will need to adapt the sort algorithm with

    var distancea = Math.abs(diffdate - a.the_date_object);
    var distanceb = Math.abs(diffdate - b.the_date_object);

edited Aug 3, 2012 at 13:14

answered Aug 3, 2012 at 13:08

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Zeta Over a year ago

+1: Nice usage of sort(). However, won't this result in a O(N log N) runtime?

Bergi Over a year ago

Sure, that depends on whether you want to get all dates in their order or just need a selection algorithm.

cantlin Over a year ago

I like this, the filter() approach hadn't occurred to me. Would also translate nicely to underscore et al.

Zeta · Accepted Answer · 2012-08-03 13:20:09Z

15

If you use an array of Date objects instead of your self-defined structure it can be achieved very easily in O(N):

var testDate = new Date(...);
var bestDate = days.length;
var bestDiff = -(new Date(0,0,0)).valueOf();
var currDiff = 0;
var i;

for(i = 0; i < days.length; ++i){
   currDiff = Math.abs(days[i] - testDate);
   if(currDiff < bestDiff){
       bestDate = i;
       bestDiff = currDiff;
   }   
}

/* the best date will be days[bestDate] */

If the array is sorted it can be achieved in O(log N) with binary search.

Edit: "it is crucial that I find both the closest match before and after the date"

var testDate = new Date(...);

var bestPrevDate = days.length;
var bestNextDate = days.length;

var max_date_value = Math.abs((new Date(0,0,0)).valueOf());

var bestPrevDiff = max_date_value;
var bestNextDiff = -max_date_value;

var currDiff = 0;
var i;

for(i = 0; i < days.length; ++i){
   currDiff = testDate - days[i].the_date_object;
   if(currDiff < 0 && currDiff > bestNextDiff){
   // If currDiff is negative, then testDate is more in the past than days[i].
   // This means, that from testDate's point of view, days[i] is in the future
   // and thus by a candidate for the next date.
       bestNextDate = i;
       bestNextDiff = currDiff;
   }
   if(currDiff > 0 && currDiff < bestPrevDiff){
   // If currDiff is positive, then testDate is more in the future than days[i].
   // This means, that from testDate's point of view, days[i] is in the past
   // and thus by a candidate for the previous date.
       bestPrevDate = i;
       bestPrevDiff = currDiff;
   }   

}
/* days[bestPrevDate] is the best previous date, 
   days[bestNextDate] is the best next date */

edited Aug 3, 2012 at 13:20

answered Aug 3, 2012 at 12:09

Zeta

106k13 gold badges205 silver badges249 bronze badges

7 Comments

Rein Over a year ago

I can add Date objects to the array, but the Dates would have to be sub-objects because each day-object also contains other (irrelevant for this question) information. Is your method also capable of searching through attributes of objects in an array and returning the objects containing the (closest matching) attributes?

Rein Over a year ago

Also, it is crucial that I find both the closest match before and after the target date, so I must always end up with two dates, unless the target date is before the first day in the array, or after the last.

Zeta Over a year ago

@ReinoudSchuijers: Added closest match. If your objects contain other information and the Date is a specific property (lets say, days[i].the_date_object, then my method is capable of doing so.

Zeta Over a year ago

@ReinoudSchuijers: The method provided above doesn't need sorted arrays. However, how are those results "strange"? Could you provide an example of your code and data?

Zeta Over a year ago

@ReinoudSchuijers: Silly me, I have accidentally used a wrong comparison. Also the start values for bestNextDiff and bestPrevDiff were wrong.

|

Talha Noyon · Accepted Answer · 2020-07-06 18:50:30Z

9

You Can try it like this

var dates = [
'July 16, 1995 03:24:00',
'Aug 18, 1995 03:24:00',
'August 19, 1995 03:24:00',
'September 17, 1995 03:24:00',
'September 14, 1995 03:24:00',
'August 18, 1995 03:24:00',
'July 16, 1995 03:24:00',
'December 15, 1995 03:24:00',
'July 13, 1995 03:24:00',
]

var temp = dates.map(d => Math.abs(new Date() - new Date(d).getTime()));
var idx = temp.indexOf(Math.min(...temp));
console.log(dates[idx]);

answered Jul 6, 2020 at 18:50

Talha Noyon

8648 silver badges14 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 11:54:50Z

7

Zeta's answer is excellent, but I was interested in how you'd approach this if you wanted to know the nearest N objects in either direction. Here's my stab:

var objects = [
    { day_year: "2012",
      day_month: "08",
      day_number: "02"
    },
    { day_year: "2012",
      day_month: "08",
      day_number: "04"
    },
    { day_year: "2012",
      day_month: "08",
      day_number: "23"
    }
];

var testDate = new Date('08/11/2012'),
    nextDateIndexesByDiff = [],
    prevDateIndexesByDiff = [];

for(var i = 0; i < objects.length; i++) {
    var thisDateStr = [objects[i].day_month, objects[i].day_number, objects[i].day_year].join('/'),
        thisDate    = new Date(thisDateStr),
        curDiff     = testDate - thisDate;

    curDiff < 0
        ? nextDateIndexesByDiff.push([i, curDiff])
        : prevDateIndexesByDiff.push([i, curDiff]);
}

nextDateIndexesByDiff.sort(function(a, b) { return a[1] < b[1]; });
prevDateIndexesByDiff.sort(function(a, b) { return a[1] > b[1]; });

console.log(['closest future date', objects[nextDateIndexesByDiff[0][0]]]);
console.log(['closest past date', objects[prevDateIndexesByDiff[0][0]]]);

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Aug 3, 2012 at 13:10

cantlin

3,2263 gold badges23 silver badges22 bronze badges

5 Comments

Rein Over a year ago

For some reason, this works for me and Zeta's answer didn't. edit: it worked before you changed it. Now I get an error (unexpected token ;) at ...? nextDateIndexesByDiff.push([i, curDiff]); : prevDateIndexesByDiff...

cantlin Over a year ago

Apologies, I added a syntax error when switching the if/else for a ternary.

Rein Over a year ago

That's ok. And for future dates, the logs could be improved by doing this:

if(nextDateIndexesByDiff.length < 1) { 	console.log("No future dates"); } else { 	console.log(['closest future date', objects[nextDateIndexesByDiff[0][0]]]); } if(prevDateIndexesByDiff.length < 1) { 	console.log("No dates in the past"); } else {	 	console.log(['closest past date', objects[prevDateIndexesByDiff[0][0]]]); }

otherwise you'll get an error.

Rein Over a year ago

There still seems to be a problem with this method. Whenever the array of dates is longer than 10, things go wrong. I use the following to generate the array:

for(var i = 0; i < 11; i++) { 	var d = new Date(); 	d.setDate(d.getDate() + i); 	full_day_array.push({day_year: d.getFullYear().toString(), day_month: (d.getMonth() + 1).toString(), day_number: d.getDate().toString()}); }

cantlin Over a year ago

See my comment on the question.

Philippe Genois · Accepted Answer · 2020-04-03 16:30:36Z

1

Here's what we use:

This function looks in array for the item which has the closest date (named dateParam) to dateToCompare.

For each item[dateParam], returns array's element which has the closest date to dateToCompare

getClosestDateInArray (array, dateParam, dateToCompare) {
  let minDiff = null;
  let mostAccurateDate = array[0];
  array.map((item) => {
    const diff = Math.abs(moment(dateToCompare).diff(item[dateParam], 'minutes', true));
    if (!minDiff || diff < minDiff) {
      minDiff = diff;
      mostAccurateDate = item
    }
  });
  return mostAccurateDate;
}

This solution require momentJS library

answered Apr 3, 2020 at 16:30

Philippe Genois

6495 silver badges7 bronze badges

Comments

Rein · Accepted Answer · 2012-08-06 10:44:21Z

This works, no matter how long the array of dates is:

function newFindClosest(dates, testDate) {
    var before = [];
    var after = [];
    var max = dates.length;
    for(var i = 0; i < max; i++) {
        var tar = dates[i];
        var arrDate = new Date(tar.day_year, tar.day_month, tar.day_number);
        // 3600 * 24 * 1000 = calculating milliseconds to days, for clarity.
        var diff = (arrDate - testDate) / (3600 * 24 * 1000);
        if(diff > 0) {
            before.push({diff: diff, index: i});
        } else {
            after.push({diff: diff, index: i});
        }
    }
    before.sort(function(a, b) {
        if(a.diff < b.diff) {
            return -1;
        }
        if(a.diff > b.diff) {
            return 1;
        }
        return 0;
    });

    after.sort(function(a, b) {
        if(a.diff > b.diff) {
            return -1;
        }
        if(a.diff < b.diff) {
            return 1;
        }
        return 0;
    });
    return {datesBefore: before, datesAfter: after};
}

Collectives™ on Stack Overflow

Find closest date in array with JavaScript

6 Answers 6

3 Comments

Edit: "it is crucial that I find both the closest match before and after the date"

7 Comments

Comments

5 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Edit: "it is crucial that I find both the closest match before and after the date"

7 Comments

Comments

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related