バイナリ検索 - 配列の要素を見つけるための最も簡単な方法の1

かなり頻繁に、プログラマー、初心者でも、特定の番号を見つけなければならない数字のセットがあるという事実に直面しました。 それは、このコレクションは、配列と呼ばれています。 そして、その中のアイテムを見つけるために、無数の方法があります。 しかし、それらのほとんどの簡単な右側のバイナリ検索考えることができます。 この方法は何ですか？ そして、どのようにバイナリ検索を実装するには？ パスカルは、このようなプログラムの組織のための最も簡単な環境ですので、我々は勉強するためにそれを使用します。

まず、分析し、この方法の利点は何ですか、それは私たちが理解できるで、 トピックの研究のポイントは何ですか。 それでは、いくつかを見つける必要があり、少なくとも億要素の大きさを持つ配列を持ってみましょう。 もちろん、この問題は簡単に私たちは、サイクルを使用している中で、単純な線形検索によって解決することができる配列であること、すべてのものに必要な要素を比較します。 問題は、このアイデアの実装は非常に時間がかかるということです。 いくつかの治療法、及び本文の3行に簡単なPascalのプログラムでは、あなたはそれを気づかないだろうが、我々は枝の数が多いと良い機能を持つ多かれ少なかれ大規模なプロジェクトに来たときに、プログラムが長すぎるためにロードすることができるようになります。 特に、コンピュータが弱いのパフォーマンスですか。 したがって、少なくとも二回の検索時間を短縮し、バイナリ検索は、そこにあります。

したがって、この方法の動作原理は何ですか？ すぐにそれはバイナリ検索が任意の配列ではなく、数字のみのソートセットで動作することを言う必要があります。 アレイの各ステップ取ら中間要素に（要素の数を意味します）。 必要に応じて 数がより多い 平均は、すべての残っていること、それが平均セル未満である、廃棄することができ、そこを見ていません。 逆に、平均よりも少ない場合には - 右にそれらの数のうち、あなたは検索することはできません。 そして、最初の要素が配列全体の真ん中要素、そして最後と最後の意志になり、新たな検索領域を選択します。 新たなフィールドの平均数は、全てのセグメントの1/4、即ち、（最後の要素+全体配列の中央要素）/ 2となります。 再度、同様の動作が行われる - 配列の平均数との比較。 目標値が平均よりも小さい場合、我々は右サイドを拒否し、また今、この中間の要素が必要ではないだろうまで、次に行うこと。

もちろん、それはバイナリ検索を作成する方法の例を見てするのが最善です。 パスカルは、誰もここに合う - バージョンは重要ではありません。 のは、簡単なプログラムを書いてみましょう。

これは、名前「マシブ」でH 1のアレイ、「NIZ」と呼ばれる検索の下限を示す変数「verh」と呼ばれる上限、平均検索語である - 「sredn」。 そして、必要な数 - 「ISK」。

だから、最初に我々は、範囲検索の上限値と下限値を割り当てます。

NIZ：= 1;
verh：=さh + 1。

次いで、「底部が上限未満になるまで、」サイクルを整理。

NIZ 始めます

各ステップで、我々は、セグメント2を分割します。

sredn：=（NIZ + verh）DIV 2。 {残りせずに分割するので、関数DIVを使用}

見直しのたびに。 メディアが望まれる場合に項目がすでに発見されているので、サイクルを中断：

іfsredn = ISKその後破ります。

所望以上の配列の中間要素は、左側を破棄した場合、つまり、平均の上限は、要素を任命します。

もしマシブ[sredn]> ISK次いでverh：= sredn。

逆にあれば、それは下限になります：

他NIZ：= sredn。
エンド;

これは、プログラムになることをすべてです。

私たちは、それが実際にバイナリの方法をどのように見えるか考えてみましょう。 1、3、5、7、10、12、18、それは数12を追求する：この配列を考えます。

合計では、7つの要素を持っているので、第四の媒体、値7であろう。

12以上、7、1.3および5つの要素以来、私たちは破棄することができます。 その後、我々は数4、4/2残基なしだから2で、新しい要素は、10の平均になります持っています。

12は10よりも大きいので、我々は7のみ10、12及び18のまま廃棄します。

ここでは、中央の要素は、それが必要な数で、すでに12です。 このタスクが完了した - 数12が見つかりました。