線形検索と二分探索：線形探索と二分探索の違い

序章

プログラミング言語での連続したメモリ割り当ては、複数のデータポイントを格納する柔軟な実装を提供します。 これは、データを分離し、すべての類似データを配列やリストなどの連続したデータ構造にマージする場合に、ピーク時に利用できます。

連続したメモリ割り当てには、コンピュータのオペレーティングシステム、データベース管理システムなどの実際のアプリケーションで多くの実装があります。アレイに新しいデータポイントを追加するには、1単位の時間が必要なため、このデータ構造は柔軟なものと見なされます。 O（1）。

ただし、実際のアプリケーションはすべてデータアクセスコマンドに依存しているため、特定のエントリを調べたり、特定のエントリを検索したりするときに問題が発生します。 そして、このタスクは、プロセッサとメモリの速度を満たすのに十分な速さである必要があります。

要素を検索するために行う比較の数に基づいて分割されたさまざまな検索アルゴリズムがあります。

配列内の各データポイントを比較して要素を検索すると、順次検索と見なされます。 ただし、一部の比較をスキップして少数の要素のみを比較している場合は、間隔検索と見なされます。 ただし、間隔検索を実行するには、配列を並べ替えた順序（昇順または降順）にする必要があります。

シーケンシャル検索の時間計算量は線形O（n）であり、バイナリ検索（間隔検索の例）の時間計算量はO（log n）です。 また、指数検索、ジャンプ検索などの他の検索アルゴリズムもあります。

ただし、線形検索とバイナリ検索が主に使用されます。線形検索はランダムまたは並べ替えられていないデータを対象とし、バイナリ検索は並べ替えおよび順序付けされたデータを対象とします。 ハッシュは、データポイントへのアクセスの時間計算量がO（1）である特別な検索アルゴリズムです。

最初に線形探索と二分探索のアルゴリズムを見ていき、次に線形探索と二分探索の違いを比較してみましょう。

線形探索

すでに説明したように、線形検索アルゴリズムは配列内の各要素を比較します。これを行うためのコードを次に示します。

コードを見ていきましょう。

配列、整数キーをパラメーターとして期待するlinear_search関数を宣言しました。 次に、すべての要素をループして、検索キーと一致するかどうかを比較する必要があるため、配列をループするforループを作成しました。その中に、その位置の数値が一致するかどうかをチェックするifループがあります。検索キーを使用するかどうか。 一致するものが見つかった場合は、その位置を返します。 配列にそのような要素がない場合は、関数の最後に-1を返します。

同じ番号の出現が複数ある場合は、最初に出現した位置を返すことに注意してください。

mainメソッドについて、整数配列を宣言して初期化しました。 次に、検索する必要のあるキーを初期化します。 ここでは配列とキーをハードコーディングしていますが、ユーザー入力に変更できます。 検索する要素とキーのリストを取得したので、線形検索メソッドが呼び出され、返されたインデックスが記録されます。 後で、戻り値を確認し、キーが存在する場合はインデックスを出力します。存在しない場合は、印刷キーが見つかりません。

二分探索

二分探索は線形探索よりも最適化されていますが、二分探索を適用するには配列を並べ替える必要があります。 そして、これを行うためのコードがあります。

コードを見ていきましょう。

ソートされた整数配列と整数キーをパラメーターとして期待するメソッドbinary_searchを宣言しました。 変数low、high、midを初期化しています。 ここで、low、highは、最初にlowが0インデックスになり、highがnインデックスになるポインタです。 では、二分探索はどのように機能しますか？

最初に、低と高の中間を計算します。 midは（low + high）/ 2として計算できますが、highが大きな数値になる場合があり、highにlowを加算すると整数オーバーフローが発生する可能性があります。 したがって、midをlow +（high-low）/2として計算するのが最適な方法です。

中央の要素を検索キーと比較し、一致するものが見つかった場合はインデックスを返します。 それ以外の場合は、中央の要素がキーよりも大きいか、キーよりも小さいかを確認します。 midが大きい場合、配列の後半のすべての要素がキーよりも大きいため、配列の前半のみをチェックする必要があります。そのため、highをmid-1に更新します。

同様に、midがkeyより小さい場合は、配列の後半を検索する必要があるため、lowをmid+1に更新します。 各反復で配列の半分の1つを無視しているため、二分探索は分割統治アルゴリズムに基づいていることを忘れないでください。

コードに戻って、mainメソッドを作成しました。 ソートされた配列と検索キーを初期化し、バイナリ検索を呼び出し、結果を出力しました。

線形検索と二分探索の両方のアルゴリズムについて説明したので、両方のアルゴリズムを比較してみましょう。

線形探索と二分探索

働く

• 線形検索はすべての要素を反復処理し、検索する必要のあるキーとそれらを比較します。
• 二分探索は、検索する必要のある配列のサイズを賢く減らし、毎回キーを中間要素と比較します。

データ構造

• 線形検索は、配列、リスト、リンクリストなどのすべてのデータ構造で柔軟に実行できます。
• 多方向トラバーサルが必要なため、すべてのデータ構造に対して二分探索を実行できるわけではありません。 したがって、単一のリンクリストのようなデータ構造は使用できません。

前提条件

• 線形検索はすべてのタイプのデータに対して実行でき、データはランダムにすることも、並べ替えることもできます。アルゴリズムは同じままです。 したがって、事前作業を行う必要はありません。
• 二分探索は、ソートされた配列でのみ機能します。 したがって、配列のソートはこのアルゴリズムの前提条件です。

使用事例

• 線形検索は、一般に、小さくランダムに順序付けられたデータセットに適しています。
• 比較的大きくソートされたデータセットには、バイナリ検索が推奨されます。

効果

• データセットが大きい場合、線形検索の効率は低下します。
• データセットが大きい場合は、バイナリ検索の方が効率的です。

時間計算量

• 線形探索では、最良の複雑さはO（1）であり、要素は最初のインデックスで見つかります。 最悪の場合の複雑さはO（n）で、要素が最後のインデックスで見つかったか、要素が配列に存在しません。
• 二分探索では、最良の複雑さはO（1）であり、要素は中央のインデックスにあります。 最悪の場合の複雑さはO（ log 2 n）です。

ドライラン

サイズが10,000の配列があると仮定します。

• 線形探索では、最良の場合の複雑さはO（1）であり、最悪の場合の複雑さはO（10000）です。
• 二分探索では、最良の場合の複雑さはO（1）であり、最悪の場合の複雑さはO（ log 2 10000）= O（13.287）です。

結論

配列でのデータアクセスの重要性を理解し、線形検索と二分探索のアルゴリズムを理解しました。 線形探索と二分探索のコードをウォークスルーしました。 線形探索と二分探索の違いを比較し、大規模な例のドライランを作成しました。

線形検索とバイナリ検索の違いに気付いたので、大きなサイズのデータ​​セットに対して両方のコードを実行して実行時間を比較し、さまざまな検索アルゴリズムの調査を開始して、それらを実装してみてください。

データサイエンスについて知りたい場合は、IIIT-BとupGradのデータサイエンスのPGディプロマをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップ、1- on-1業界のメンター、400時間以上の学習、トップ企業との仕事の支援。

世界のトップ大学からオンラインでデータサイエンスコースを学びましょう。 エグゼクティブPGプログラム、高度な証明書プログラム、または修士プログラムを取得して、キャリアを早急に進めましょう。