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

Question

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

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

我如何有效地找到小于或等于任意值的最大数。我试图创建的功能如下：

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

最简单的方法是每次迭代集合。但是，我正在寻找一种方法来加快速度。我可以将其转换为另一种格式，例如 an IDictionary，但想不出一个聪明的方法来临时做这件事。

Answer 1

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

使用 Array.BinarySearch。如果输入在列表中，它将返回索引，如果不是，则返回第一个较大值的索引的补码。您只需反转结果并减去一个以获得最接近的较小值的索引。

Answer 2

如果您无法控制列表的生成，二进制搜索可能是您的最佳选择

*注意：这是伪代码，并不打算涵盖所有边缘条件

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