How to calculate the time percentage of any time in an array of date objects in Javascript

Question

I have a sorted array of Javascript date objects, the array always has a length of 14 entries. In pseudo:

dates
["label1"] = date object 1,
["label2"] = date object 2,
...
["label14"] = date object 14

Although they are in sorted order by date, the dates are not distributed evenly. For example, between entry 1 and 2 may be 1 hour, whilst between entry 5 and 6 are a few minutes, or a few hours.

My challenge is to find an algorithm that for any given input date, will find the following from this array:

• The position in the array of the previous date
• The position in the array of the next date
• Our input date will fall in between the above dates, I'd like to know the percentage in time between the 2 points. For example, exactly in between the dates would return 50%.

I don't like asking "please code this for me" questions but I'm really no good in writing efficient alghorithms and have been unsuccesful in finding an existing alghorithm.

Answer 1

Since the array is sorted, the previous date is at the previous position in the array while the next date is at the next position in the array.

To determine the percentage, you can simply use the following formula:

var percentage = (date - prev) / (next - prev);

That will result in a number between 0 and 1, so if you need between 0 and 100%, simply multiply by 100.

Example:

var dates = [];
for (var i=0; i<14; i++) { dates.push(new Date(1392119656126 + i*i*10000000)) }
for (var i = 1; i<dates.length-1; i++) { 
  var percentage = ((dates[i]-dates[i-1])/(dates[i+1]-dates[i-1])) * 100;
  console.log('P', dates[i-1], 'C', dates[i], 'N', dates[i+1], 'PERC', percentage);
}

Answer 2

ou can use a binary search for that value. Adapted from this answer:

function index(arr, date) { // binary search
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        if (arr[m] < date) 
            l = m + 1;
        else if (arr[m] > date)
            r = m - 1;
        else // +arr[m] == +date
            return m;
    }
    if (l==0) return -1;
    if (l==arr.length) return l;
    return l-1+(date-arr[l-1])/(arr[l]-arr[l-1]);
}

Example:

> var dates=[new Date(0), new Date(100), new Date(500)]
> index(dates, new Date(-1))
-1
> index(dates, new Date(0))
0
> index(dates, new Date(50))
0.5
> index(dates, new Date(70))
0.7
> index(dates, new Date(100))
1
> index(dates, new Date(150))
1.125
> index(dates, new Date(500))
2
> index(dates, new Date(600))
3

So when you get a result from such an index call, you would

• first check whether it's outside the boundaries res < 0 || res >= length
• get the previous position by Math.floor(res)
• get the next position by Math.ceil(res)
• get the percentage between them by (res%1)*100