An algorithm to find the closest values in javascript array

Question

I'm working on a small algorithm to find the closest values of a given number in an random array of numbers. In my case I'm trying to detect connected machines identified by a 6-digit number ID ("123456", "0078965", ...) but it can be useful for example to find the closest geolocated users around me.

What I need is to list the 5 closest machines, no matter if their IDs are higher or lower. This code works perfectly but I'm looking for a smarter and better way to proceed, amha I got to much loops and arrays.

let n = 0; // counter
let m = 5; // number of final machines to find

// list of IDs founded (unordered: we can't decide)
const arr = ["087965","258369","885974","0078965","457896","998120","698745","399710","357984","698745","789456"] 
let NUM = "176789" // the random NUM to test

const temp = [];
const diff = {};
let result = null;

// list the [m] highest founded (5 IDs)
for(i=0 ; i<arr.length; i++) {
    if(arr[i] > NUM) {
        for(j=0 ; j<m; j++) {
            temp.push(arr[i+j]);
        } break;
    }
}

// list the [m] lowest founded (5 IDs)
for(i=arr.length ; i>=0; i--) {
    if(arr[i] < NUM) {
        for(j=m ; j>=0; j--) {
            temp.push(arr[i-j]);
        } break;
    }
}

// now we are certain to get at least 5 IDs even if NUM is 999999 or 000000

temp.sort(function(a, b){return a - b}); // increase order

for(i=0 ; i<(m*2); i++) {
    let difference = Math.abs(NUM - temp[i]);
    diff[difference] = temp[i]; // [ 20519 : "964223" ]
}

// we now get a 10-values "temp" array ordered by difference
// list the [m] first IDs:

for(key in diff){
    if(n < m){
        let add = 6-diff[key].toString().length; 
        let zer = '0'.repeat(add);
        let id = zer+diff[key]; // "5802" -> "005802"
        result += (n+1)+":"+ id +" ";
        n+=1;
    }
}

alert(result);

-> "1:0078965 2:087965 3:258369 4:357984 5:399710" for "176789"

Answer 1

A few good approaches so far, but I can't resist throwing in another.

This tests a sliding window of n elements in a sorted version of the array, and returns the one whose midpoint is closest to the value you're looking for. This is a pretty efficient approach (one sort of the array, and then a single pass through that) -- though it does not catch cases where there's more than one correct answer (see the last test case below).

const closestN = function(n, target, arr) {
  // make sure we're not comparing strings, then sort:
  let sorted = arr.map(Number).sort((a, b) => a - b); 
  target = Number(target);

  let bestDiff = Infinity; // actual diff can be assumed to be lower than this
  let bestSlice = 0;       // until proven otherwise

  for (var i = 0; i <= sorted.length - n; i++) {
    let median = medianOf(sorted[i], sorted[i+n-1]) // midpoint of the group
    let diff = Math.abs(target - median);           // distance to the target
    if (diff < bestDiff) {  // we improved on the previous attempt
      bestDiff = diff;      // capture this for later comparisons                         
      bestSlice = i;
    }
    // TODO handle diff == bestDiff? i.e. more than one possible correct answer
  }
  return sorted.slice(bestSlice, bestSlice + n) 
}

// I cheated a bit here; this won't work if a > b:
const medianOf = function(a, b) { 
  return (Math.abs(b-a) / 2) + a
}

console.log(closestN(5, 176789, ["087965", "258369", "885974", "0078965", "457896", "998120", "698745", "399710", "357984", "698745", "789456"]))

// more test cases
console.log(closestN(3,   5, [1,2,5,8,9])) // should be 2,5,8
console.log(closestN(3,   4, [1,2,5,8,9])) // should be 1,2,5
console.log(closestN(1,   4, [1,2,5,8,9])) // should be 5
console.log(closestN(3,  99, [1,2,5,8,9])) // should be 5,8,9
console.log(closestN(3, -99, [1,2,5,8,9])) // should be 1,2,5
console.log(closestN(3,  -2, [-10, -5, 0, 4])) // should be -5, 0, 4
console.log(closestN(1,   2, [1,3]))  // either 1 or 3 would be correct...

Answer 2

You could take an array as result set, fill it with the first n elements and sort it by the delta of the wanted value.

For all other elements check if the absolute delta of the actual item and the value is smaller then the last value of the result set and replace this value with the actual item. Sort again. Repeat until all elements are processed.

The result set is ordered by the smallest delta to the greatest by using the target value.

const
    absDelta = (a, b) => Math.abs(a - b),
    sortDelta = v => (a, b) => absDelta(a, v) - absDelta(b, v),
    array = [087965, 258369, 885974, 0078965, 457896, 998120, 698745, 399710, 357984, 698745, 789456],
    value = 176789,
    n = 5,
    result = array.reduce((r, v) => {
        if (r.length < n) {
            r.push(v);
            r.sort(sortDelta(value));
            return r;
        }
        if (absDelta(v, value) < absDelta(r[n - 1], value)) {
            r[n - 1] = v;
            r.sort(sortDelta(value));
        }
        return r;
    }, []);

console.log(result); // sorted by closest value

Answer 3

You actually don't need to have so many different iterations. All you need is to loop twice:

1. The first iteration attempt is to use .map() to create an array of objects that stores the ID and the absolute difference between the ID and num
2. The second iteration attempt is simply to use .sort() through the array of objects created in step 1, ranking them from lowest to highest difference

Once the second iteration is done, you simply use .slice(0, 5) to get the first 5 objects in the array, which now contains the smallest 5 diffs. Iterate through it again if you want to simply extract the ID:

const arr = ["087965","258369","885974","078965","457896","998120","698745","399710","357984","698745","789456"];
let num = "176789";
let m = 5; // number of final machines to find

// Create an array of objects storing the original arr + diff from `num`
const diff = arr.map(item => {
  return { id: item, diff: Math.abs(+item - +num) };
});

// Sort by difference from `num` (lowest to highest)
diff.sort((a, b) => a.diff - b.diff);

// Get the first m entries
const filteredArr = diff.slice(0, m).map(item => item.id).sort();

// Log
console.log(filteredArr);

// Completely optional, if you want to format it the way you have in your question
console.log(`"${filteredArr.map((v, i) => i + ": " + v).join(', ')}" for "${num}"`);