リスト内の要素を検索して前の要素を取得する（両方とも高速である必要があります）

Question

O（n）よりも素早く要素を見つけることができるデータ構造またはソリューションを探していますと見つかった要素の前の要素を取得します

私のケースでは、が既に埋め込まれてソートされています。、DateTimeで要素を見つける必要があり、以前のx要素を返す必要があります。

私はLinkedListで試しましたが、検索が遅すぎましたo（n）。 私はDateTimeで見つけることができるように辞書を使うことも考えましたが、前の要素を得るために逆順にループする方法はわかりません。

class FinancialQuote 
{ 
    public DateTime TradingDate; 
    public double Price; 

    protected bool Equals(FinancialQuote other) 
    { 
     return TradingDate.Equals(other.TradingDate); 
    } 
} 

public void Main() 
{ 

    var quotes = new LinkedList<FinancialQuote>(); 
    // quotes are populated here 

    var result = new List<FinancialQuote>(); 
    var howManyQuotes = 2; 

    // the goal here is to find quote4 and returns quote3 and quote2 
    var currentNode = quotes.Find(quote4); // O(N) which is too slow 

    for (int i = 0; i < howManyQuotes; i++) 
    { 
     var previousClose = currentNode.Previous.Value; 
     result.Add(previousClose); 

     currentNode = currentNode.Previous; 
    } 
} 

だから私の変数をもたらすはずがquote3とquote2

Answer 1

が含まれていますが、日付でソートされている必要があり、通常のList<FinancialQuote>使用する必要があります。

BinarySearchを使用して、DateTimeを挿入するインデックスを指定します。リスト作成にもこの機能を使用してください。これは、dateTimeが見つかった場合は正のインデックス（完全一致）を返し、このdatetimeを挿入する必要がある負のインデックスを返します。

このインデックスを上限として使用します。 （検索されたインデックスに0を反復する）

Answer 2

Listタイプは、すでにインデックスで要素にアクセスするためのO（1）時間を保証します。したがって、バイナリ検索アルゴリズムを適用してソートされたリストの要素を見つけるためにO（logN）時間を達成することができます。

その後、その要素の先祖を繰り返し処理するだけで済みます。

int index = quotes.BinarySearch(searchValue); 

if (index >= 0) 
{ 
    int lowIndex = Math.Max(index - howManyQuotes, 0); 
    for (int cur = lowIndex; cur <= index; cur++) 
    { 
     // do something with quotes[cur]; 
    } 
}