Finding a number in an Array closest to mine

Question

I am fairly new to javascript and I'm having problems finding the most efficient way to calculate the problem below

I have an array of objects. Each object has a time stamp and a total field. I have a number saved as a variable and I want to loop through the array to find the timestamp of the object with the total field closest to my number.

This is a sorted array so the numbers are always increasing so for example the numbers could look like this:

Jan 125 
Feb 150 
Mar 200 
Apr 275

If the number I have is 205 I would like to get the result Mar back.

They are objects taken from a mongoDb so look something like this

{TimeStamp: "2013-06-24 01:00", Delivered: 464, Queued: 39, Total: 503}
{TimeStamp: "2013-07-02 01:00", Delivered: 485, Queued: 37, Total: 522}
{TimeStamp: "2013-07-05 01:00", Delivered: 501, Queued: 41, Total: 542}
{TimeStamp: "2013-07-08 09:48", Delivered: 501, Queued: 64, Total: 565}

They are objects taken from a mongoDb so look something like this { TimeStamp: "2013-07-08 09:48", Delivered: 501, Queued: 64, Total: 565 } — Marty Cochrane, Jul 08 '13 at 08:25
This is not very clear, you should add the sample array of objects and clarify on which property of object you're trying to search. — Okan Kocyigit, Jul 08 '13 at 08:30

Ja͢ck · Accepted Answer · 2015-03-23T02:31:00.320

If the list is already sorted on the right field, you can use this code to find the minimum distance in O(n):

var data = [
    {total: 125, name: 'Jan'}, 
    {total: 150, name: 'Feb'}, 
    {total: 200, name: 'Mar'}, 
    {total: 275, name: 'Apr'}
];

function getClosest(arr, value) 
{
    var closest, mindiff = null;

    for (var i = 0; i < arr.length; ++i) {
        var diff = Math.abs(arr[i].total - value);

        if (mindiff === null || diff < mindiff) {
            // first value or trend decreasing
            closest = i;
            mindiff = diff;
        } else {
            // trend will increase from this point onwards
            return arr[closest];
        }
    }
    return null;
}

You keep track of the currently closest object and its corresponding (absolute) difference between the total and the searched value.

You keep updating those two values as long as the difference decreases. When that no longer happens you can return immediately, because you know it will never decrease afterwards.

To use it:

getClosest(data, 200);

Please not. If you only need the minimum, don't sort the whole array. — Bergi, Jul 08 '13 at 08:44

Edorka · Answer 2 · 2013-07-08T09:58:45.977

0

var numbers = [122,231,323,53];
var myNumber = 200;
var difference = 9999; 
var nearest = null;
for (i = 0 ; i < numbers.lenght; i++){
    var candidate = numbers[i];
    var currentDifference = Math.abs(myNumber - candidate);
    if  (currentDifference  < difference) {
        nearest = candidate; difference = currentDifference;
    }
}

edited Jul 08 '13 at 09:58

answered Jul 08 '13 at 08:27

Edorka

1,781
12
24

Your code doesn't work. Don't you forget to copy here method initialization with argument 'myNumber'? – Maxim Zhukov Jul 08 '13 at 08:31

georg · Answer 3 · 2013-07-08T08:44:09.670

I've got this helpful generic function:

function min(ary, key) {
    return ary.map(function(x) {
        return [key ? key(x) : x, x]
    }).reduce(function(m, x) {
        return x[0] < m[0] ? x : m;
    })[1]
}

It finds a minimal element in the array using key as a comparison function. Applied to your problem:

 number = ...
 closestTimestamp = min(arrayOfRecords, function(record) {
       return Math.abs(number - record.total)
 }).TimeStamp;

score 0 · Answer 4 · edited May 23 '17 at 12:28

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

function nearestIndex(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // this[m] equals the element
            return m;
    }
    // now, l == r+1
    // usually you would just return -1 in case nothing is found
    if (l == arr.length) return r;
    if (r == 0) return 0;
    if (Math.abs(compare(arr[l])) > Math.abs(compare(arr[r]))) // "closer"
        return r;
    else
        return l;

}

var items = […];
var i=nearestIndex(items, function(x){return x.Total-532;}); // compare against 532
console.log(items[i].TimeStamp);

Finding a number in an Array closest to mine

4 Answers4