二分探索

1. 二分探索
二分探索は半探索とも呼ばれ、より効率的な探索方法です。
二分探索要件: 線形テーブルは順序付きリスト、つまりテーブル内のノードがキーワードによって順序付けされており、テーブルの記憶構造としてベクトルが使用されます。シーケンス テーブルは昇順であると仮定できます。

2. 二分探索の基本的な考え方
二分探索の基本的な考え方は次のとおりです: (R[low..high] が現在の探索間隔であると仮定します)
(1) 最初に区間の中点の位置を決定します。 :
(2) 次に、チェックする K 値を R[mid].key と比較します。等しい場合、検索は成功し、この位置が返されます。そうでない場合は、新しい検索間隔を決定する必要があり、二分検索が続行されます。具体的な方法は以下の通りです:
① R[mid] .key>K の場合、テーブルの順序性から R[mid..n].keys がすべて K より大きいことがわかります。テーブル内に K に等しいキーを持つノードがある場合、そのノードはサブテーブル R[1..mid-1] の位置 Mid の左側にある必要があります。新しい検索間隔は左側のサブテーブル R[1.mid-1] です。 .mid-1]。
②同様に、R[mid].key したがって、最初の検索間隔 R[1..n] から開始して、現在の検索間隔の中間位置のノード キーワードと比較するたびに、検索が成功したかどうかを判断できます。成功すると、現在の検索範囲が半分になります。このプロセスは、キー K を持つノードが見つかるまで、または現在の検索間隔が空になる (つまり、検索が失敗する) まで繰り返されます。

3. 二分探索アルゴリズム

int BinSearch(SeqList R, KeyType K)
int low=1, high=n, Mid; //現在の探索間隔の上限と下限を設定します
; Low+High)/2;
If (R [MID] .Key == K) return Mid; // 正常に返される
if (r [mid] .kdy & gt; k)
hIGH = mid-1; / R[low..mid-1] で検索を続ける
アウト アウト アウト スルー スルー スルー スルー スルー スルー スルー スルー スルー スルー スルー オフ スルー オフ‐ ‐ ‐ スルー ‐ スルー ‐ ‐‐‐‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ 1 検索間隔が空で、検索は失敗しました
} //BinSeareh
二分探索アルゴリズムは再帰的プログラムを与えるのも簡単です [演習を参照]

4.
アルゴリズムの入力インスタンス内のキーワードを順序付けます。シーケンスは
(05、13、19、21、37、56、64、75、80、88、92) です。
検索されるキーワード K は 21 とそれぞれ85。具体的な検索プロセス [アニメーションのデモを参照]

5. 二分探索決定木

二分探索プロセスは二分木で説明できます。現在の検索間隔の中央にあるノードがルートとして使用され、その中のノードがルートとして使用されます。左サブテーブルと右サブテーブル それぞれルートの左サブツリーと右サブツリーとして。結果として得られる二分木は、二分探索を記述する決定木 (Decision Tree) または比較木 (Comparison Tree) と呼ばれます。
注:
デシジョン ツリーの形状はテーブル ノードの数 n にのみ関係し、入力インスタンスの R[1..n].keys の値とは関係ありません。
【例】11個のノードからなる順序付きリストは下図のような決定木で表現できます。

(1)二分探索決定木の構成
①円ノードは木の内部ノードです。ツリー内の円ノード内の番号は、順序付きリスト内のノードの位置を示します。
②外部ノード: 円ノード内のすべてのヌルポインタが仮想四角ノード、つまり外部ノードに置き換えられます。
③ツリー内のノードiとその左(右)の子を繋ぐ左(右)の枝にあるマーク「<」、「(」、「>」、「)」は、検索対象のキーワードK<のときを示します。 ; R[i].key(K>R[i].key) の場合、左 (右) の分岐をたどって i の左 (右) の子に到達し、さらに子のキーワードを K と比較する必要があります。それらが等しい場合、検索プロセスは終了して戻ります。そうでない場合は、K をツリーの下位レベルのノードと比較し続けます。

(2)二分探索決定木の探索
二分探索とは、与えられた値Kと二分探索決定木のルートノードのキーワードを比較することです。等しい場合、成功。それ以外の場合、ルート ノードのキーより小さい場合は、左側のサブツリーを検索します。キーワードがルート ノードより大きい場合は、右側のサブツリーを検索します。
【例】11 個のノードがあるテーブルの場合、検索対象のノードがテーブル内の 6 番目のノードの場合は 1 回の比較のみが必要ですが、検索中のノードがテーブル内の 3 番目または 9 番目のノードの場合は 2 回の比較が必要です。 1 番目、4 番目、7 番目、10 番目のノードを見つけるには 3 回の比較が必要で、2 番目、5 番目、8 番目、11 番目のノードを見つけるには 4 回の比較が必要です。
成功した二分探索プロセスは、デシジョン ツリーのルートからチェック対象のノードまでのパスを正確にたどっており、比較されたキーワードの数はツリー内のノードのレベル数とまったく同じであることがわかります。検索が失敗した場合、比較プロセスは決定木のルートから外部ノードまでのパスを通過し、必要なキーワード比較の数は、パス上の内部ノードの総数になります。
【例】検索するテーブルのキーワード列は (05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92) K=85 のレコードを検索します。内部ノードは 6、9、10 で、最終的に正方形ノード「9-10」に到達し、比較数は 3 になります。
実際、正方形ノードの「i-i+1」の意味は、検索対象の値 K が R[i].key と R[i+1].key の間にある、つまり R[ i].key

(3)二分探索の平均探索長
内部ノードの総数が n=2h-1 であると仮定すると、ツリーは深さ h=lg(n+1) の完全なバイナリ ツリーであると判断されます (深さ h は異なります)外部ノードを含む)。ツリーの k 番目のレベルのノードの数は 2k-1 で、それらを見つけるために必要な比較の数は k です。したがって、確率が等しいと仮定すると、二分探索が成功した場合の平均検索長は、
ASLbn≈lg(n+1)-1
二分探索が失敗した場合、比較する必要があるキーワードの数は異なります。最悪の場合、成功した比較の数は決定木の深さを超えません。つまり、2 点検索の最悪のパフォーマンスと平均パフォーマンスは非常に近いものになります。

6. 二分探索の長所と短所

二分探索は効率的ですが、テーブルをキーワードでソートする必要があります。並べ替え自体は非常に時間のかかる作業です。効率的な並べ替え方法を使用した場合でも、O(nlgn) 時間かかります。

二分探索は順次ストレージ構造にのみ適用されます。テーブルの順序を維持するには、シーケンシャル構造での挿入および削除中に多数のノードを移動する必要があります。したがって、二分探索は、一度作成するとめったに変更されず、頻繁に検索が必要になる線形テーブルに特に適しています。
検索がほとんど必要なく、頻繁に変更が必要な線形テーブルの場合、リンク リストを格納構造として使用して、順次検索を実行できます。二分探索はリンクリストには実装できません。

バイナリソート

#include

#include

void TwoInsertSort(int array[],int n)
{
int left, right, num; while( right >= left) // 2 点メソッド 挿入位置を見つける {
middle = (left + right)/2 // ソートされた中間位置を指す
if (num & lt; array [middle]) //
Right = 左の区間の middle-1;
Else // 次の要素は右の区間にある必要があります
left = middle+1
}
for (j = i-1; j & gt; = left ; //後方ソートコードが R[i] より大きいレコード
array[j+1] = array[j];

int rcmp( const int *a, const int *b)
{
return (*a-*b);
}
void main()
{
int array[50];
int i;
printf("元の配列は :n");
for( i=0; i {
array[i] = 50-i;
printf("array[%d ]: %dn", i, array[i]);
}
TwoInsertSort(array,sizeof(array)/sizeof(int));//バイナリソート
printf("nAftersorted:n");
for( i =0; i printf("array[%d]:%dn", i, array[i]);

//ライブラリ関数 bsearch は、順序付けされたアイテム内の特定の項目を検索します。配列番号を返し、その番号のアドレスを返します

a = (int *)bsearch(&b, numarray, sizeof(umarray)/sizeof(umarray[0]), sizeof(int),rcmp);

}

二分探索に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。