4

Lets say I have an array with numbers like this:

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31];

It is sorted in ascending order, now, let's say I pick a value x:

var x = 13;

How do I find which two values that are closest to x?

In this case it would be 12 and 15, but how do I get these two for any given x, and in case x is lower than the lowest, then only return the lowest, and if it's greater than the greatest, return only the greatest, like if x = 3, then only return one value, 4?

I have tried this:

function getClosest(a, x) {
    for (var i = 0; i < a.length - 1; i++) {
        var c1 = a[i],
            c2 = a[i + 1];

        if (x > c1 && x < c2) return [c1, c2];
        else if (i == 0) return [c1];
        else if (i == a.length - 2) return [c2];
    }
}

Now, this is my approach, how would you solve this/what is the most efficient solution to this?

  • why do you think your code is sloppy? what sort of approach would be better exactly? – omarjmh Jun 12 '16 at 19:59
  • 5
    code review may be better for this question – michaelmesser Jun 12 '16 at 20:00
  • Seems fine to me, though you could do a binary search as well since the array is sorted. Will be more efficient on large arrays. –  Jun 12 '16 at 20:00
  • I am thinking, how would someone else approach this problem, this is my approach, but maybe there is better solutions that anyone hasn't though of that is much better. –  Jun 12 '16 at 20:01
  • @2426021684 Not how it's currently stated, but it could turn into one. – Mast Jun 12 '16 at 20:08
  • What should happen in the event that, with your posted array, someone tried to find the closest number to `12` - a number already present in the array? Should `12` be returned (since it's the closest possible number) or discounted since it's the same number? Or even if they were searching for a number outside of the bounds of the array, `0` or `32` for example, should the first, or last, two numbers from the array be returned? – David Thomas Jun 12 '16 at 20:20
  • same question with good answer http://stackoverflow.com/questions/8584902/get-closest-number-out-of-array – avim101 Jun 12 '16 at 20:21
  • @mavim Never say "same question" if it's not. This is about the two, or one closest values, not the single closest. –  Jun 13 '16 at 03:35
  • @DavidThomas Yes if it's 12, return only 12, if it's out of range, return only the closest, otherwise, always return the two closest –  Jun 13 '16 at 03:36
  • just a late question: if you have `x = 19` should the result be `[18, 19]` or `[19, 20]`? the distance of both answers is equal. – Nina Scholz Jun 13 '16 at 06:22
  • 1
    @NinaScholz Only [19], and the distance doesn't have to do with anything –  Jun 13 '16 at 11:56
  • 4
    I'm voting to close this question as off-topic because this question belongs on Code Review – Anders Marzi Tornblad Jun 14 '16 at 08:47
  • 1
    @AndersTornblad The reason you gave does not actually explain why the question is off-topic for Stack Overflow. [Please stick to bona fide closure reasons documented in the Help Center.](http://meta.stackoverflow.com/q/313266/1157100) – 200_success Jun 14 '16 at 09:55

7 Answers7

2

You could use Array#some and a short circuit.

function closest(value, array) {
    var result = [];
    array.some(function (a) {
        if (a > value) {
            return result.push(a);
        }
        result = [a];
        return a === value;
    });
    return result;
}

console.log(closest(13, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]));
console.log(closest(3, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]));
console.log(closest(50, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]));
console.log(closest(19, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]));
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
1

I believe your code does not work as expected, because it will return the first element if the first two elements are smaller than your x. Also you are missing the case that x is in a.

Your code has linear runtime while returning directly if the correct answer is found.

Because a is sorted you can optimise your code to be O(log n) by using a binary search approach.

Make a[0] and a[n] your upper and lower bounds. Compare x with a[n/2]. If x < a[n/2] set your upper bound to a[n/2] elsewise set your lower bound to a[n/2]. Compare x to the element between your new bounds and continue as described until your upper and lower bound are consecutive. Then return them.

Take care of the cases that x < min(a) and x > max(a) beforehand. Take care of the case x in a separately.

xuma202
  • 1,074
  • 1
  • 10
  • 22
1

Assuming the array is sorted, you can use a binary search. It will only be O(lg n), less than your O(n) approach.

function lowerBound(arr, x, from=0, to=arr.length) {
  if(from >= to) return to-1;
  var m = Math.floor( (from+to)/2 );
  if(a[m] < x) return lowerBound(arr, x, m+1, to);
  return lowerBound(arr, x, from, m);
}
function upperBound(arr, x, from=0, to=arr.length) {
  if(from >= to) return to;
  var m = Math.floor( (from+to)/2 );
  if(a[m] > x) return upperBound(arr, x, from, m);
  return upperBound(arr, x, m+1, to);
}
function getClosest(a, x) {
  var lb = lowerBound(a, x),
      ub = upperBound(a, x, lb+1),
      res = [];
  if(lb >= 0) res.push(a[lb]);
  if(ub < a.length) res.push(a[ub]);
  return res;
}
Oriol
  • 274,082
  • 63
  • 437
  • 513
0

This is slightly different approach with sort() and slice()

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31];

function getClosest(num, ar) {
  if (num < ar[0]) {
    return ar[0];
  } else if (num > ar[ar.length - 1]) {
    return ar[ar.length - 1];
  } else {
    return ar.sort((a, b) => Math.abs(a - num) - Math.abs(b - num)).slice(0, 2);
  }
}

console.log(getClosest(11, a))
Nenad Vracar
  • 118,580
  • 15
  • 151
  • 176
0

Here is fast solution which also covers lowest and highest boundaries:

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31];

function getClosest(a, x) {
    var min = Math.min.apply(null, a), max = Math.max.apply(null, a), i, len;

    if (x < min) {   // if x is lower than the lowest value
        return min; 
    } else if (x > max) {  // if x is greater than the 'greatest' value
        return max;
    }
    a.sort();
    for (i = 0, len = a.length; i < len; i++) {
        if (x > a[i] && x < a[i + 1]) {
            return [a[i], a[i + 1]];
        }
    }
}

console.log(getClosest(a, 13));   // [12, 15]
console.log(getClosest(a, 3));    // 4
console.log(getClosest(a, 33));   // 31
console.log(getClosest(a, 25));   // [23, 27]
RomanPerekhrest
  • 88,541
  • 4
  • 65
  • 105
0

Look for array if number exists. If not, push it to array. Sort array, and get index of that number. If that number is first (zeroth) entry return second element of array (arr[1]). If it is last, return the element before. Else return right and left neighbours.

function closest_two(n, arr) {
    if (arr.indexOf(n) == -1) {
        arr.push(n);
    }
    arr.sort(function(a,b) { return a-b; })
    p = arr.indexOf(n);
    if (p==0) { return arr[1]; }
    if (p == (arr.length - 1)) { return arr[p-1]; }

  return[arr[p-1], arr[p+1]]
}
0

My approach would be: If x is not in a, push x onto a and then resort. Then, let i=indexOf(x), then return a[i-1] if it exists, and a[i+1] if it exists. a is cloned, since push modifies it.

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31];
function neighbors(a,x){
b=a.slice(0);//clone a
if (a.indexOf(x) < 0) {//push x onto a if x not in a
    b.push(x);
    b.sort((a,b)=>a-b); //resort
    }
var i=b.indexOf(x);
return [i-1 in b ? b[i-1] : null, i+1 in b ? b[i+1] : null].filter(Number);
}

neighbors(a,13);//[12,15]
neighbors(a,12);//[9,15]
neighbors(a,5);//[4,7]
neighbors(a,4);//[5]
neighbors(a,3);//[4]
neighbors(a,27);//[23,31]
neighbors(a,28);//[27,31]
neighbors(a,31);//[27]
neighbors(a,32);//[31]
chiliNUT
  • 18,989
  • 14
  • 66
  • 106