javascript - JavaScript配列で最も近い次の値を検索

Question

次のような JavaScript 配列がvar test = [2,5,8,12,56];あり、9 の最も近い次の値を検索したいので、この場合の出力は 12 です (8 ではありません!)。

Answer 1

さて、これを行う簡単な方法は次のとおりです。

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
}

検索値が配列にある場合に何を返すかを言わないので、それを返したいと思います。「最も近い次の値」によって、常に検索値よりも大きい次の数値を返す必要があることを意味する場合は、 の代わりにarr[i] >= val使用するように変更します。>>=

大きな配列がある場合は、最初から実行するのではなく、おそらくある種のバイナリソートが必要です。

Answer 2

配列がソートされている場合に試すことができるものは次のとおりです。境界の場合に合わせて調整する必要があります。これはアルゴリズムのアイデアのためだけです...

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]

Answer 3

非常に単純なコードを以下に示します。これがあなたを助けることを願っています

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

ここで動作するものを参照してください

Answer 4

1配列を並べ替えることから始め、を使用してarr.sort();、値を昇順（3,6,4,7,1 --> 1,3,4,6,7）で並べ替え、次に繰り返します。

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

Answer 5

配列が常にソートされることがわかっている場合、または事前に配列をソートすることが合理的である場合 (たとえば、配列があまり頻繁に変更されないが、多くの取得が必要な場合)、ソートされた配列に対してバイナリ検索を使用できます。配列。

配列内に値が見つからない場合は、指定された値より大きい最小の要素を示す上限が返されます。これにより、平均で O(log n) の複雑さが得られますが、単純なアプローチ (配列全体をループする) では、平均で O(n) の複雑さが得られます。

// 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;
}