2

たまたまソートされた固定の数値セットがあるとします。

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

任意の値以下の最大数を効率的に見つけるにはどうすればよいでしょうか。私が作成しようとしている関数は次のとおりです。

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

最も簡単な方法は、毎回セットを反復処理することです。ただし、これを高速化する方法を探しています。これを などの別の形式に変換してIDictionaryも問題ありませんが、これをオフハンドで行う賢い方法は思いつきません。

4

2 に答える 2

2

非常によく似た質問がここで回答されました。

Array.BinarySearch を使用します。入力がリストにある場合はインデックスを返し、リストにない場合は最初に大きい値のインデックスの補数を返します。結果を逆にして 1 を引くだけで、最も近い小さい値のインデックスを取得できます。

于 2013-06-11T18:34:15.970 に答える
0

リストの生成を制御できない場合は、おそらくバイナリ検索が最適なオプションです。

*注: これは疑似コードであり、すべてのエッジ条件をカバーすることを意図したものではありません

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
    }
}
于 2013-06-11T18:27:50.497 に答える