数字列表-如何有效地找到小于或等于N的最大值

本文关键字：最大值 小于 列表 有效地 数字 | 更新日期: 2023-09-27 18:17:59

假设我有一组固定的数字，这些数字恰好是排序的:

static readonly int[] numbers = new int {
    1, 200, 204, 228, 298, 300, 331, 332, ... 2983
};

我如何有效地找到小于或等于任意值的最大数字。我试图创建的函数如下所示:

public int LessThanOrEqualTo(int n)
{
    // ???
}

最简单的方法是每次迭代该集合。然而，我正在寻找一种方法，使这更快。我可以将其转换为另一种格式，例如IDictionary，但无法立即想到一种聪明的方法。

数字列表-如何有效地找到小于或等于N的最大值

这里回答了一个非常相似的问题。

Array.BinarySearch使用。如果输入在列表中，它将返回索引，如果不在列表中，它将返回第一个较大值的索引的补集。你只需要把结果反过来，然后减去1，就可以得到最接近的小值的索引。

如果你不能控制列表的生成，二进制搜索可能是你最好的选择

*注意:这是伪代码，它不打算覆盖所有的边缘条件

FindLargestLessThan(int val, int[] arr, int hi, int lo)
{
    if(hi == lo)
    {
        // it's either arr[hi] or the element immediately before that.
    }
    else if(arr[(hi+lo)/2] > val)
    {
        return FindLargestLessThan(val, arr, (hi+lo)/2, lo)
    }
    else if(arr[(hi+lo)/2] < val)
    {
        return FindLargestLessThan(val, arr, hi, (hi+lo)/2)
    }
    else if(arr[(hi+lo)/2] == val)
    {
        //found it
    }
    else
    {
        //oops
    }
}
相关文章：