14

Listを見ていると、いくつかのオーバーロードがあるBinarySearchメソッドが表示されますが、Listにそのようなメソッドを含めることがまったく意味があるのか​​どうか疑問に思わずにはいられません。

リストがソートされていない限り、なぜバイナリ検索を実行したいのですか？また、リストが並べ替えられていない場合、メソッドを呼び出すことはCPU時間の無駄になります。そのメソッドをリストに含めることのポイントは何ですか？

4

9 に答える 9

24

他の正解に加えて、二分探索を正しく書くのは驚くほど難しいことに注意してください。多くのコーナーケースといくつかのトリッキーな整数演算があります。バイナリ検索は明らかにソートされたリストでの一般的な操作であるため、BCLチームは、顧客に独自のバイナリ検索アルゴリズムを作成するように勧めるのではなく、バイナリ検索アルゴリズムを一度正しく作成することで世界にサービスを提供しました。それらの顧客が作成したアルゴリズムのかなりの数が間違っているでしょう。

于 2010-07-15T14:19:51.273 に答える
20

並べ替えと検索は、リストで非常に一般的な2つの操作です。通常のリストでバイナリ検索を提供しないことによって開発者のオプションを制限することは不親切です。

ライブラリの設計には妥協が必要です-.NET設計者は、C＃の配列とリストの両方でバイナリ検索機能を提供することを選択しました。これは、これらが便利で一般的な操作であると感じた可能性があり、それらを使用することを選択したプログラマーが前提条件を理解しているためです。 （つまり、リストが順序付けられていること）それらを呼び出す前に。

List<T>オーバーロードの1つを使用してソートするのは簡単Sort()です。ソートを保証する不変条件が必要だと感じた場合は、いつでもSortedList<TKey,TValue>またはSortedSet<T>代わりに使用できます。

于 2010-07-15T13:48:55.540 に答える
9

BinarySearchwithでのみ意味があるのとList<T>同じように、ソートされたaでのみ意味があります。面倒ですが、対処する必要があります。機能Xが基準Yに依存する場合があります。Yが常に真であるとは限らないという事実がXを役に立たなくするわけではありません。IList<T>.AddIList<T>IsReadOnly = false

さて、私の意見では、.NETに実装のための一般的な メソッドSortとBinarySearchメソッドがないことはイライラします（たとえば、拡張メソッドとして）。もしそうなら、ランダムアクセスを提供する非読み取り専用コレクション内のアイテムを簡単に並べ替えて検索することができます。 IList<T>

そうすれば、いつでも自分で書くことができます（または他の人のをコピーすることもできます）。

于 2010-07-15T14:08:19.320 に答える
6

BinarySearch他の人は、ソートされたで非常に役立つと指摘していList<T>ます。List<T>ただし、C ++ STLの経験がある人なら誰でもすぐにわかるように、実際には属していません。

ISortedList<T> : IList<T>最近のC＃言語の開発では、ソートされたリストの概念を定義し（たとえば）、そのインターフェイスの拡張メソッドとして定義する（など）方が理にかなってBinarySearchいます。これは、よりクリーンで直交性の高いタイプのデザインです。

Nito.Linqライブラリの一部としてそれを始めました。最初の安定したリリースは数か月以内になると思います。

于 2010-07-15T14:04:55.803 に答える
3

はい。ただし、ListにはSort（）メソッドもあるため、BinarySearchの前に呼び出すことができます。

于 2010-07-15T13:46:03.563 に答える
3

検索と並べ替えはアルゴリズムのプリミティブです。標準ライブラリには、高速で信頼性の高い実装があると便利です。そうでなければ、開発者は車輪の再発明に時間を浪費します。

ただし、.NET Frameworkの場合、アルゴリズムの特定の選択により、アルゴリズムの有用性が低下する可能性があるのは残念です。場合によっては、それらの動作が定義されていません。

  1. List<T>.BinarySearchリストに同じ値の要素が複数含まれている場合、メソッドは1つのオカレンスのみを返し、必ずしも最初のオカレンスではなく、いずれかのオカレンスを返す可能性があります。

  2. List<T>この実装は不安定なソートを実行します。つまり、2つの要素が等しい場合、それらの順序は保持されない可能性があります。対照的に、安定ソートでは、等しい要素の順序が保持されます。

同じくらい高速な決定論的アルゴリズムがあり、これらはビルディングブロックとしてはるかに役立つため、これは残念です。Python、Ruby、Goのバイナリ検索アルゴリズムがすべて最初に一致する要素を見つけることは注目に値します。

于 2014-02-19T15:34:26.427 に答える
2

ソートされていないリストでBinarySearchを呼び出すのは完全に馬鹿げていることに同意しますが、大きなリストがソートされていることがわかっている場合は完璧です。

ストリームからのアイテムが100,000アイテム以上の（多かれ少なかれ）静的リストに存在するかどうかをチェックするときに使用しました。

リストのバイナリ検索は、list.Findを実行するよりも桁違いに高速です。これは、データベースの検索よりも桁違いに高速です。

私は理にかなっています、そして私はそこでそれをうれしく思います（そうでなければそれを実行することはロケット科学であるというわけではありません）。

于 2010-07-15T13:56:36.463 に答える
1

おそらく別のポイントは、配列が同じようにソートされていない可能性があるということです。したがって、理論的には、配列にBinarySearchを設定することも無効になる可能性があります。

ただし、高級言語のすべての機能と同様に、データを理解している理由のある人が適用する必要があります。そうしないと、失敗します。確かに、いくつかのクロスチェックを適用することができ、「IsSorted」というフラグを立てることができます。そうしないと、バイナリ検索で失敗しますが、....。

于 2017-08-18T14:02:15.973 に答える
0

いくつかの擬似コード：

if List is sorted
   use the BinarySearch method
else if List is not sorted and you think sorting it is "waste of CPU time"
   use a different algorithm that is more suitable and efficient
于 2017-09-26T21:04:44.457 に答える