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 e 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 e to me seem overly plex: 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.

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 e 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 e to me seem overly plex: 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.

• javascript
• arrays
• algorithm

• is the array always sorted? – Nina Scholz Commented Dec 11, 2016 at 18:59
• That is always the array - in that order. It's static. – SpaceNinja Commented Dec 11, 2016 at 18:59
• what value would you like to get if you have [1, 3] and the look up value is 2? 1 or 2? – Nina Scholz Commented Dec 11, 2016 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 Commented Dec 11, 2016 at 19:16
• 1 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 Commented Dec 11, 2016 at 19:19

4 Answers 4

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

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 es 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.

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 pareNumbers = (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(pareNumbers)[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

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.