1

C# 4.0 のソート済みリストでバイナリ検索オプションを使用したいと考えています。私は古い二分探索を見てきました：

C# を使用して範囲指定された値の範囲を検索するにはどうすればよいですか?

binarySearch を使用して 2 つの日付の間で範囲検索を行う方法について、助けが必要です。多くの日付を持つリストがあり、2 つの日付の間でこの大きなリストをすばやく検索し、見つかったアイテムがあればそれを返したいと考えています。バイナリ検索は、ソートされているときに不要な比較をすばやく削除できるため、高速です。

4

2 に答える 2

1

仮定:

  • 特定の型 T のコレクション、順序付きリスト、または配列があります。
  • このコレクションはバッグ(重複は許可されています) であり、セット(ユニークなアイテム) ではありません。

必要がある

  • バイナリ検索を実行して、「from」基準 (下限) を満たすアイテムを見つけます。

    これはバイナリ検索であり、 setではなくbagがあるため、これが from 基準を満たすコレクション内の最初の項目であるとは限りません。それはあなたがする必要があることを意味します...

  • 「from」基準に一致する最初の項目に戻ります。これは順次操作です。

    この時点で、反復の開始点が得られます。あなたがしなければならないのは、この時点からコレクションを順番に反復することです...

  • 「スルー」基準では、上限条件は真です。

これは、上限テストと下限テストの両方にカスタム比較子を使用することを示唆している可能性があります。

また、LINQy 拡張メソッドの形式で解決策を提案する場合もあります。

幸運を！

于 2012-08-03T17:34:09.173 に答える
1

リストが List で、日付が DateTime であると仮定すると、この方法で List.BinarySearch(...) を実行できます

List<DateTime> l;
int startIndex = l.BinarySearch(beginDate);
int endIndex = l.BinarySearch(endDate);

この時点で、beginDate と endDate の間の日付の範囲ができました。これで、2 つのインデックス間で反復処理を行うことができます。

正確な日付が見つからなかった場合に最も近い日付を見つけたい場合は、バイナリ検索を実行できません。その場合、データ構造を再実装する必要があります (この場合、List を何らかの強力な構造に置き換える必要があります)。これは、毎年格納する二分探索ツリーと各ノードが格納される範囲検索アルゴリズムをサポートします。その年に属するすべての月を含む新しい二分探索木を含むようになり、各ノードにはその月のすべての日を含む新しい二分探索木が含まれるようになります。

于 2012-08-03T16:20:48.257 に答える