CODEWITHSUNDEEP
javascript
Jilco Tigchelaar
Jilco Tigchelaar

Reputation: 2149

Search closest next value in javascript array

I have a javascript array like var test = [2,5,8,12,56]; and now I want to search the closest next value of 9. So the output is 12 in this case (and not 8!).

Upvotes: 2

Views: 2402

Answers (5)

Mattias Buelens
Mattias Buelens

Reputation: 20159

If you know the array is always going to be sorted or if it is reasonable to sort the array beforehand (e.g. when the array doesn't change very often but you need a lot of retrievals), you can use a binary search on the sorted array.

If the value is not found in the array, the upper bound is returned which indicates the smallest element greater than the given value. This gives O(log n) complexity on average whereas the naive approach (looping over the whole array) gives O(n) complexity on average.

// Binary search
// Adapted from http://jsfromhell.com/array/search
function binarySearch(arr, val, insert) {
    var high = arr.length, low = -1, mid;
    while (high - low > 1) {
        mid = (high + low) >> 1;
        if (arr[mid] < val) low = mid;
        else high = mid;
    }
    if (arr[high] == val || insert) {
        return high;
    } else {
        return -1;
    }
}

function getClosestNext(arr, val) {
    // Get index
    var i = binarySearch(arr, val, true);
    // Check boundaries
    return (i >= 0 && i < arr.length) ? arr[i] : null;
}

Upvotes: 0

Prasad
Prasad

Reputation: 701

A very simple code is given below. Hope this will help you

   var test = [2,5,8,12,56];
var key = 9;
var closestNext=1000;
for(var i=0;i<test.length;i++)
{
    if(test[i] > key)
    {
         if(test[i]<closestNext)
         {
             closestNext = test[i];
         }
    }

} 

alert(closestNext);
​

see the working one here

Upvotes: 1

Elias Van Ootegem
Elias Van Ootegem

Reputation: 76395

1 Start by sorting the array, using arr.sort();, just sorts the values in the ascending order (3,6,4,7,1 --> 1,3,4,6,7), then just iterate: 

function getNext(inputVal,arr)
{
    arr.sort();;
    for (var i=0;i<arr.lenght;i++)
    {
        if (arr[i] >= inputVal)
        {
            return arr[i];
        }
    }
    throw new Error('Out of range');
}

Upvotes: 0

Bharat Sinha
Bharat Sinha

Reputation: 14363

Here is what you can try if the array is sorted, you need to tune for for boundry cases, this is just for idea of algorithm...

NUM is input
TEST is your array
INDEX is index variable

For INDEX from 0 .. TEST.SIZE -1 
    IF NUM > TEXT[INDEX]
        RETURN TEXT[INDEX]

Upvotes: 1

nnnnnn
nnnnnn

Reputation: 150040

Well here's a simple way to do it:

function getNextVal(arr, val) {
    // omit the next line if the array is always sorted:
    arr = arr.slice(0).sort(function(a,b){return a-b;});

    for (var i=0; i < arr.length; i++)
        if (arr[i] >= val)
            return arr[i];

    // return default value when val > all values in array
}

You don't say what to return if the search value is in the array, so I've assumed you want to return it. If by "closest next value" you meant that it should always return the next number higher than the search value change arr[i] >= val to use > instead of >=.

If you have a large array you probably want some kind of binary sort instead of just going through from the beginning.

Upvotes: 6

Related Questions