Matching a number to closest number in a set in Javascript

Question

I have an array of values, and I need a function that takes in two integers, and assigns those two integers to their closest values from the array.

var bandwidthSteps = [0.128, 0.256, 0.512, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 22, 25, 30, 40, 50, 55, 60, 80, 90, 100, 110, 128, 200, 256, 300, 350, 400, 450, 500];

When a "private" value and a "guest" value come in, I need to match each to their closest value in the set - rounded down.

var function = closestValues(private,guest) {
    //
};

So when this function is given 14 and 21, I need the function to return:

private = 15
guest = 20

since those are the closest matches to integers in the array. Note that the "steps" in the array are irregular, it's not like 2, 5, 8, 11. Or else it would be easy.

The solution in a JS function would be great, or the correct direction to go in making such a function. The ideas that come to me seem overly complex: for each set of two consecutive numbers in the array, average the two and then determine if the given integer is greater or less than the average, etc etc. I'm sure there is a more concise way.

what value would you like to get if you have `[1, 3]` and the look up value is `2`? `1` or `2`? — Nina Scholz, Dec 11 '16 at 19:10
It must round down, so if the given number is 3, it would be matched to the closest integer in the array rounded down, so 2. — SpaceNinja, Dec 11 '16 at 19:16
So it would be 1 in your example. In the case where the given number sits exactly between two numbers in the array, it must round down to the lower of the two. — SpaceNinja, Dec 11 '16 at 19:19
Possible duplicate of [get closest number out of array](http://stackoverflow.com/questions/8584902/get-closest-number-out-of-array) — rlemon, Dec 11 '16 at 19:52

Nina Scholz · Accepted Answer · 2016-12-11T19:52:33.407

You could iterate the array and check with the absolute delta and the last delta.

function closestValue(v) {
    var value,
        lastDelta;

    bandwidthSteps.some(function (a) {
        var delta = Math.abs(v - a);
        if (delta >= lastDelta) {
            return true;
        }
        value = a;
        lastDelta = delta;
    });
    return value;
}

var bandwidthSteps = [0.128, 0.256, 0.512, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 22, 25, 30, 40, 50, 55, 60, 80, 90, 100, 110, 128, 200, 256, 300, 350, 400, 450, 500];

console.log(closestValue(14));
console.log(closestValue(21));

score 2 · Answer 2 · edited Oct 12 '18 at 21:36

I'd

first map the array to a pair of [distance, index in the original array]
then sort it and pick the first element
and use it's index to get the value in the original array.

var compareNumbers = (a, b) => a[0] - b[0];

var closestValue = function( arr, item ){
    return arr[
        arr.map(
            function(a,key){ 
                return [Math.abs(a-item),key]; 
         }).sort(compareNumbers)[0][1]
     ];
}

//
// test it
//
var bandwidthSteps = [0.128, 0.256, 0.512, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 22, 25, 30, 40, 50, 55, 60, 80, 90, 100, 110, 128, 200, 256, 300, 350, 400, 450, 500];

console.log(closestValue( bandwidthSteps, 14))
// 15
console.log(closestValue( bandwidthSteps, 21))
//  20

Edited to compare numbers, otherwise, and considering https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort, numbers are converted to strings and give wrong results — Pandaiolo, Oct 12 '18 at 21:04

blazs · Answer 3 · 2016-12-13T10:13:51.730

If the array is sorted and only contains 32 elements, I suggest you benchmark how linear search performs against binary search (as described below). I am very interested in seeing the numbers. (Linear search exploits locality, so maybe it will outperform binary search on small enough arrays.)

You can use binary search to discover the closest number as follows. Whenever a new element comes in, do a binary search for the element; when the binary search terminates, return the number at the latest valid index in the binary search (this is a number closest to the query number); binary search runs in O(log n) time where n=size of the array.

score 1 · Answer 4 · answered Dec 11 '16 at 19:07

I won't give you a written algorithm, but the general idea: Have a variable of lowestDifference, initially set to JavaScript's Infinity. Iterate over the array, calculate the difference between the input number (or numbers for that matter) and the current number in the array (use Math.abs on the result). If the difference is lower than the lowestDifference, save it to lowestDifference and save the array element to a variable denoting the answer. And to be precise to your requirement, in case the difference is equal to the lowestDifference, change the answer to the new array element only if it's lower than the input number.

Matching a number to closest number in a set in Javascript

4 Answers4