38

すべてのプログラマーは、二分探索がデータの順序付けられたリストを検索する優れた高速な方法であると教えられています。二分探索を使用したおもちゃの教科書の例はたくさんありますが、実際のプログラミングではどうでしょうか: 二分探索は実際のプログラムのどこで使用されるのでしょうか?

4

22 に答える 22

27

二分探索はどこでも使用されます。任意の言語ライブラリ（Java、.NET、C ++ STLなど）から並べ替えられたコレクションを取得すると、それらはすべてバイナリ検索を使用して（または使用するオプションがあり）、値を検索します。それを実装する必要があることはめったにありませんが、それを利用するには、その背後にある原則を理解する必要があります。

于 2009-02-12T07:35:04.953 に答える
23

バイナリ検索を使用すると、メモリ スペースが不足している場合に、順序付けられたデータにすばやくアクセスできます。100.000 個の 32 ビット整数のセットを検索可能で順序付けられたデータ構造に格納したいが、セットを頻繁に変更しないとします。400.000 バイトのソートされた配列に整数を簡単に格納でき、バイナリ検索を使用して高速にアクセスできます。しかし、それらを B ツリー、RB ツリー、または「より動的な」データ構造に配置すると、メモリ オーバーヘッドが発生し始めます。たとえば、左の子ポインターと右の子ポインターがある任意の種類のツリーに整数を格納すると、少なくとも 1.200.000 バイトのメモリが消費されます (32 ビット メモリ アーキテクチャを想定)。もちろん、できる最適化はありますが、それが一般的な仕組みです。

順序付けられた配列を更新する (挿入または削除を行う) のは非常に遅いため、配列が頻繁に変更される場合、二分探索は役に立ちません。

二分探索を使用したいくつかの実用的な例を次に示します。

  • ケース ラベルが個別の整数である仮想マシンに「switch() ... case:」構造を実装する。100 ケースの場合、二分探索を使用して 6 ～ 7 ステップで正しいエントリを見つけることができます。条件分岐のシーケンスは平均 50 回の比較を行います。
  • 辞書順で検索可能な文字列のセットのすべてのサフィックスを含むサフィックス配列を使用して、部分文字列の高速検索を実行します (メモリを節約し、実装をシンプルに保ちたいと考えました)。
  • 方程式の数値解を見つける (あなたが怠け者で、ニュートン法を実装することを気にしない場合)
于 2009-02-12T17:47:27.027 に答える
15

すべてのプログラマーは、デバッグ時にバイナリ検索を使用する方法を知っている必要があります。

プログラムがあり、プログラムの実行中の特定の時点でバグが表示されていることがわかっている場合は、バイナリ検索を使用して、実際に発生した場所を特定できます。これは、コードの大部分をシングルステップで実行するよりもはるかに高速です。

于 2009-02-12T07:31:34.480 に答える
7

二分探索は優れた高速な方法です。

STL や .NET フレームワークなどが登場する前は、独自のカスタマイズされたコレクション クラスを作成する必要がある状況に遭遇することがよくありました。ソートされた配列がデータの保存に適した場所である場合は常に、バイナリ検索がその配列内のエントリを見つける方法になります。

二分探索は今日でも広く使用されていると確信していますが、利便性のためにライブラリによって「内部」で処理されています。

于 2009-02-12T05:38:23.703 に答える
6

BTree 実装でバイナリ検索を実装しました。

BTree 検索アルゴリズムは、読み取る次のノード ブロックを見つけるために使用されましたが、4K ブロック自体 (キー サイズに基づくキーの数を含む) 内では、レコード番号 (リーフ ノードの場合) を見つけるためにバイナリ検索が使用されました。 ) または次のブロック (非リーフ ノードの場合)。

バランスの取れた二分木のように、チェックごとに残りの検索スペースの半分を削除するため、逐次検索と比較して非常に高速です。

于 2009-02-12T05:48:24.350 に答える
4

私はかつて、グラフに2次元データを表示するGUIコントロール用に（これが実際に二分探索であるとは知らずに）実装しました。マウスでクリックすると、データカーソルがx値に最も近いポイントに設定されます。多数のポイント（数千、x86が100 MHzを超えるCPU周波数を取得し始めたときのことです）を処理する場合、これはインタラクティブには実際には使用できませんでした。最初から線形検索を実行していました。少し考えた後、分割統治法でこれに取り組むことができると思いました。すべてのエッジケースで機能するようになるまで、少し時間がかかりました。

これが確かに基本的なCSアルゴリズムであることを私が知ったのはほんの少し後のことでした...

于 2009-02-12T07:42:30.473 に答える
3

その一例が stl セットです。基礎となるデータ構造は、二分探索による O(log n) でのルックアップ、挿入、および削除をサポートするバランスの取れた二分探索ツリーです。

もう 1 つの例は、対数時間で実行される整数除算アルゴリズムです。

于 2009-02-12T05:37:33.490 に答える
3

私たちのコードでは、数千の ACLS を 1 秒間に何千回も検索するために、今でも頻繁に使用しています。ファイルから取得した ACL は静的であり、起動時にアレイに追加する際にアレイを拡張する費用が発生する可能性があるため、これは便利です。走ると猛烈に速い。

最大で 7 回の比較/ジャンプ (8 回で 511 回、9 回で 1023 回など) で 255 要素の配列を検索できる場合、バイナリ検索がほぼ最速であることがわかります。

于 2009-02-12T06:02:16.953 に答える
2

二分探索は現在、3D ゲームやアプリケーションの 99% で使用されています。空間を木構造に分割し、二分探索を用いて、3D 位置とカメラに応じて表示するサブディビジョンを取得します。

その最初の最大のショーケースの 1 つは Doom でした。二分木と関連する検索により、レンダリングが強化されました。

于 2010-03-04T14:42:13.587 に答える
1

いくつかの計算を実行するためにコレクションを反復処理するプログラムがありました。これは非効率的だと思ったので、コレクションを並べ替えてから、単一のバイナリ検索を使用して関心のあるアイテムを見つけました。私はこのアイテムとそれに一致する隣人を返しました。私は事実上、コレクションをフィルタリングしました。

これを行うことは、コレクション全体を繰り返して一致するアイテムを探し出すよりも実際には時間がかかりました。

並べ替えと検索のパフォーマンスが最終的に反復に追いつくことを知って、コレクションにアイテムを追加し続けました。速度が同じになるまで、約600個のオブジェクトのコレクションが必要でした。1000個のオブジェクトには明らかなパフォーマンス上の利点がありました。

また、使用しているデータの種類、重複、および拡散についても検討します。これは、並べ替えと検索に影響します。

私の答えは、両方の方法を試して時間を計ることです。

于 2009-08-07T15:10:16.683 に答える
1

バイナリソートは、テキストボックスの寸法が一定のテキストのサイズに合わせてフォントを調整するのに役立ちます

于 2012-04-08T09:05:14.930 に答える
1

hg bisectの基礎です

于 2010-03-04T15:59:29.573 に答える
1

デジタル タイミングまたはアナログ レベルの測定に使用される半導体テスト プログラムでは、二分探索が広く使用されます。Advantest、Teradyne、Verigy などの自動テスト装置 (ATE) は、入力ロジックを適用し、デジタル パーツの出力状態を検証する真理値表ブラスターと考えることができます。

入力ロジックが各サイクルの時間 = 0 で変化し、入力ロジックが変化してから X ns 遷移する単純なゲートを考えてみてください。T=X の前に出力をストローブすると、ロジックは期待値と一致しません。時間 T=X より後にストローブし、ロジックは期待値と一致します。バイナリ検索を使用して、ロジックが一致しない最新の値と一致する最も早い部分の間のしきい値を見つけます。これは、移行時間を測定する簡単な方法です。同じ手法を使用して、セットアップ時間、ホールド時間、動作可能な電源レベル、電源対遅延などを解決できます。

あらゆる種類のマイクロプロセッサ、メモリ、FPGA、ロジック、および多くのアナログ ミックスド シグナル回路は、テストと特性評価に二分探索を使用します。

-- マイク

于 2009-02-12T07:51:08.737 に答える
1

とりわけ、コマンド名のテーブルとそのコマンドを解釈する関数へのポインターを備えたインタープリターがあります。約60のコマンドがあります。線形検索を使用するのはそれほど面倒ではありませんが、私は二分検索を使用します。

于 2009-02-12T06:03:12.303 に答える
0

Pythonのlist.sort()メソッドはTimsortを使用します。Timsortは（AFAIK）バイナリ検索を使用して要素の位置を特定します。

于 2010-02-14T21:00:39.933 に答える
0

.NETSortedDictionaryは舞台裏でバイナリ ツリーを使用していると思います (STL マップによく似ています)。そのため、バイナリ検索を使用して要素にアクセスします。SortedDictionary

于 2009-08-07T15:15:58.437 に答える
0

方程式の根を見つけることは、二分探索のような非常に簡単なアルゴリズムでやりたいことの 1 つです。

于 2009-02-16T06:20:44.120 に答える
0

二分探索は、多くの既製のマップ/辞書の実装にはない機能を提供します: 非完全一致を見つけることです。

たとえば、バイナリ検索を使用して、GPS ログに基づいて写真のジオタグを実装しました。すべての GPS ウェイポイントをタイムスタンプで並べ替えた配列に配置し、バイナリ検索を使用して、各写真のタイムスタンプに最も近いウェイポイントを識別します。

于 2010-03-04T14:54:10.743 に答える
0

Delphi を使用すると、ソートされた TStringList 内の文字列を検索しながらバイナリ検索を楽しむことができます。

于 2009-05-06T07:34:14.800 に答える
-1

配列で検索する要素のセットがある場合は、それらのそれぞれを線形に検索するか、配列を並べ替えてから、同じ比較述語で二分検索を使用できます。後者ははるかに高速です。

于 2009-02-12T05:39:08.180 に答える