Find the nearest date in an array using JavaScript

Question

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

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

I also added a timestamp attribute for each daily object 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 for them.

Now I want to find the next two days to any date. Therefore, if an array with days contains

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

And I'm looking for August 11, 2012, I want him to return on August 4, 2012 and August 23, 2012.

I tried using the 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) way to do this?

Edit: "However, how are these results" weird "? Could you give an example of your code and data?"

Now I use the following to create 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, using the code below, works only for an array of ten dates or shorter. When I use an array of 11 or more dates, the results are unexpected.

For example: using an array of 15 dates from August 6, 2012 to August 21, 2012. If I then call findClosest(full_day_array, new Date("30/07/2012"); you 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}; } 

Answer 1

This works no matter how long the date array 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}; } 

Answer 2

You can easily use the sort function with the special 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 the results before or after diffdate , you can filter the array for this:

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

---

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

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

Answer 3

If you use an array of Date objects instead of your self-defined structure, this 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 reached in O (log N) with binary search.

Edit: "It is very important that I find 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 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 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 */ 

Answer 4

The answer to Zeta's is excellent, but I was interested in how you approach this if you want to know the nearest N objects in any direction. Here is my hit:

 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]]]);