Find the closest index to given value

Question

I have an ordered array:

btnDrag.pos = [0, 65, 131, 196, 259, 323, 388, 453, 517];

And a function that fires when drag stops:

btnDrag.draggable({
    axis: 'x',
    containment: 'parent',
    stop: function() {
        var index = (function(){
            var new_x = btnDrag.position().left;
            // now, how to find the closest index in btnDrag.pos relative to new_x ?
            // return index;
        })();
        btnDrag.animate({
            'left': (btnDrag.pos[index] + 'px')
        });
    }
});

The array values are points which btnDrag is allowed to stay (in axis 'x').

So, the function must return the closest index with the value to btnDrag go.

Thanks in advance.

possible dublicate: http://stackoverflow.com/questions/8584902/get-closest-number-out-of-array — Alex, Aug 07 '15 at 12:38
Check this fiddle-[http://jsfiddle.net/dsov5am8/](http://jsfiddle.net/dsov5am8/). my answer is similar to the second one. So posting as comment. — Amit.rk3, Aug 07 '15 at 12:57

Holt · Answer 1 · 2020-10-29T12:51:07.147

Since your array is sorted, the fastest way is to use a modified version of the binary search algorithm:

function closest (arr, x) {
    /* lb is the lower bound and ub the upper bound defining a subarray or arr. */
    var lb = 0, 
        ub = arr.length - 1;
    /* We loop as long as x is in inside our subarray and the length of our subarray is
       greater than 0 (lb < ub). */
    while (ub - lb > 1) {
        var m = parseInt((ub - lb + 1) / 2); // The middle value
        /* Depending on the middle value of our subarray, we update the bound. */
        if (arr[lb + m] > x) {
            ub = lb + m;
        }
        else if (arr[lb + m] < x) {
            lb = lb + m;
        }
        else {
            ub = lb + m; 
            lb = lb + m;
        }
    }
    /* After the loop, we know that the closest value is either the one at the lower or 
       upper bound (may be the same if x is in arr). */
    var clst = lb;
    if (abs(arr[lb] - x) > abs(arr[ub] - x)) {
        clst = ub;
    }
    return clst; // If you want the value instead of the index, return arr[clst]
}

Here is a fiddle where you can test it: http://jsfiddle.net/Lpzndcbm/4/

Unlike all the solution proposed here this solution runs in O(log(n)) and not in O(n). If you are not familiar with complexity, it means that this algorithm will find the closest value in an array of size N in at most O(log(N)) loop while the others will find it in at most N loop (with N = 10000, it makes a big difference since log(10000) ~ 14 (binary log)).

Note that if you have really small array, this may be slower than the naive algorithm.

It isn't working: _http://jsbin.com/yinajitojo/edit?js,console_ — , Aug 07 '15 at 13:12
@WashingtonGuedes Sorry, I made some stupid mistakes while moving from python to javascript ;) Answer updated, it should work now, you can check here http://jsfiddle.net/Lpzndcbm/ (I cannot access jsbin from where I am... ). — Holt, Aug 07 '15 at 13:44

nobe4 · Accepted Answer · 2015-08-07T12:55:23.753

2

There you go :

function closest(list, x) {
    var min,
        chosen = 0;
    for (var i in list) {
        min = Math.abs(list[chosen] - x);
        if (Math.abs(list[i] - x) < min) {
            chosen = i;
        }
    }
    return chosen;
}

Each time, the minimum distance is computed and the chosen value is updated based on the minimum. (http://jsbin.com/dehifefuca/edit?js,console)

edited Aug 07 '15 at 12:55

answered Aug 07 '15 at 12:40

nobe4

2,802
3
28
54

It works nice... but I need the index instead the value. Because in my code I have more than one array with same length... So, if I could find the index in this first array, then in the next ones I can only acces the values by this index. – Aug 07 '15 at 12:54
I've edited my answer, there was very little change to do :) – nobe4 Aug 07 '15 at 12:55
Thank you.. It is working now – Aug 07 '15 at 13:00

score 1 · Answer 3 · answered Aug 07 '15 at 12:39

1

Something like this?

var closest = btnDrag.pos.reduce(function (prev, curr) {
 return (Math.abs(curr - new_x) < Math.abs(prev - new_x) ? curr : prev);
});

answered Aug 07 '15 at 12:39

LcKjus

121
6

This looks promising, but It doesn't work here – Aug 07 '15 at 12:56
Great answer. Readable and concise! Thanks – Phil Mander Nov 16 '15 at 16:21

score 0 · Answer 4 · answered Aug 07 '15 at 12:56

Simple for loop will do it:

var btnDrag = {};
btnDrag['pos'] = [0, 65, 131, 196, 259, 323, 388, 453, 517]; 
new_x = 425;


    var index = -1;

    for (var i = 0; i < btnDrag.pos.length; i++)
    {
        if (i < btnDrag.pos.length-1) //loop till i is at 2 positions from the end.
        {
           //value has to be less then the selected value + 1
           if (new_x < btnDrag.pos[i+1])
           {

               //calculate the half between the values and add it with the first value
               // test if new_x is larger then that value.
               if ((btnDrag.pos[i+1] - btnDrag.pos[i])/2 + btnDrag.pos[i] > new_x) 
               {
                   index = i;
                   break;
               }
               else
               {
                   index = i+1;
                   break;
               }
           }
        }
        else
        {
           //edge cases.
           if (new_x < 0)
           {
                index = 0;
           }
           else
           {
              index = btnDrag.pos.length-1;
           }      
       
        }
    }

document.body.innerHTML = btnDrag['pos'][index] + " (" + index + ")";

Find the closest index to given value

4 Answers4