在 javascript 数组中搜索最接近的下一个值

Search closest next value in javascript array

本文关键字：下一个 最接近 搜索 javascript 数组      更新时间：2023-09-26

我有一个像var test = [2,5,8,12,56];这样的javascript数组，现在我想搜索最接近的下一个值9。所以在这种情况下，输出是 12（而不是 8！

这里有一个简单的方法可以做到这一点：

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的下一个数字，以使用 > 而不是 >= 。

如果你有一个大数组，你可能想要某种二进制排序，而不仅仅是从头开始。

如果数组被排序，您可以尝试这样做，您需要针对边界情况进行调整，这只是为了算法的想法......

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]
下面

给出了一个非常简单的代码。希望这对你有帮助

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

在此处查看工作

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

如果您知道数组总是要排序，或者事先对数组进行排序是合理的（例如，当数组不经常更改但您需要大量检索时），则可以对排序后的数组使用二叉搜索。

如果在数组中找不到该值，则返回上限，指示大于给定值的最小元素。这平均给出了 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;
}
相关文章：