二分探索アルゴリズム：機能、利点、時間と空間の複雑さ

序章

どの計算システムでも、検索は開発するのに最も重要な機能の1つです。 検索手法は、ファイルの取得、インデックス作成、およびその他の多くのアプリケーションで使用されます。 利用可能な多くの検索手法があります。 その1つが二分探索手法です。

二分探索アルゴリズムは、反復ごとにリストの半分を無視するという考えに基づいて機能します。 指定されたリストで探している値が見つかるまで、リストを分割し続けます。 二分探索アルゴリズムは、単純な線形探索アルゴリズムへの迅速なアップグレードです。

コーディングの経験は必要ありません。 360°キャリアサポート。 IIIT-BおよびupGradの機械学習とAIのPGディプロマ。

二分探索アルゴリズムの働き

最初に注意することは、バイナリ検索アルゴリズムは常にソートされたリストで機能するということです。 したがって、最初の論理的な手順は、提供されたリストを並べ替えることです。 ソート後、リストの中央値が目的の値でチェックされます。

• 目的の値が中央インデックスの価値と等しい場合、インデックスは回答として返されます。

• ターゲット値がリストの中央インデックスの取引よりも低い場合、リストの右側は無視されます。

• 目的の値が中央インデックスの値より大きい場合、左半分は破棄されます。

• 次に、ターゲット値が見つかるまで、ショートリストでこのプロセスが繰り返されます。

例1

例を使ってアルゴリズムを見てみましょう。 次の番号のリストがあると仮定します。

1、15、23、7、6、14、8、3、27

目的の値を27とします。リスト内の要素の総数は9です。

最初のステップは、リストを並べ替えることです。 並べ替えると、リストは次のようになります。

1、3、6、7、8、14、15、23、27

リスト内の要素の数は9であるため、中央のインデックスは5になります。 インデックス5の値は8です。目的の値27は、値8と比較されます。最初に、値が8に等しいかどうかを確認します。 はいの場合、インデックスを返して終了します。

27は8より大きいため、左側を無視し、リストの右側のみをトラバースします。 トラバースする新しいリストは次のとおりです。

14、15、23、27

注：実際には、リストは切り捨てられません。 観測のみが絞り込まれます。 したがって、「新しいリスト」を、新しいリストを作成したり、元のリストを短縮したりすることと混同しないでください。 新しいリストで実装することもできますが、2つの問題があります。 まず、メモリのオーバーヘッドが発生します。 新しいリストごとに、スペースが複雑になります。 次に、元のインデックスを反復ごとに追跡する必要があります。

新しい中央インデックスは、実装に応じて、2番目または3番目の要素と見なすことができます。 ここでは、3番目の要素を中心と見なします。 値23は値27と比較されます。値は中央値よりも大きいため、左半分を破棄します。

トラバースするリストは次のとおりです。

27

リストには要素が1つしかないため、中心的な要素と見なされます。 したがって、目的の値を27と比較します。それらが一致すると、元のリストの27のインデックス値を返します。

例2

同じリストで、目的の値を2と仮定します。

まず、中心値8が2と比較されます。目的の値が中心値よりも小さいため、リストの左側に焦点を絞ります。

新しいトラバーサルは次のもので構成されます。

1、3、6、7

中央の要素を2番目の要素として取り上げましょう。 目的の値2が3と比較されます。値がさらに小さいため、フォーカスをリストの左側に絞り込みます。

新しいトラバーサルは次のもので構成されます。

1

トラバースリストには要素が1つしかないため、値は残りの要素と直接比較されます。 値が一致していないことがわかります。 したがって、エラーメッセージでループから抜け出します：値が見つかりません。

データサイエンスの高度な認定、250以上の採用パートナー、300時間以上の学習、0％EMI

時間と空間の複雑さ

二分探索アルゴリズムの時間計算量はO（log n）です。 中央のインデックスが目的の値に直接一致する場合、最良の時間計算量はO（1）になります。 最悪のシナリオは、リストの端にある値またはリストにない値のいずれかである可能性があります。

二分探索アルゴリズムのスペースの複雑さは、アルゴリズムの実装によって異なります。 それを実装する2つの方法があります：

1. 反復法
2. 再帰的方法

どちらの方法もまったく同じですが、実装に2つの違いがあります。 まず、再帰的メソッドにはループがありません。 次に、新しい値をループの次の反復に渡すのではなく、次の再帰に渡します。 反復法では、反復はループ条件を介して制御できますが、再帰法では、最大値と最小値が境界条件として使用されます。

反復法では、空間の複雑さはO（1）になります。 再帰的方法では、スペースの複雑さはO（log n）になります。

利点

• 二分探索アルゴリズムは、実装するのに非常に単純な探索アルゴリズムです。

• これは線形検索に比べて大幅に改善されており、実装が難しい検索アルゴリズムのいくつかと比較してほぼ同じように実行されます。

• 二分探索アルゴリズムは、リストを順番に組み合わせるのではなく、反復ごとにリストを半分に分割します。 大きなリストでは、この方法は非常に便利です。

チェックアウト：ディシジョンツリーの分類：知っておくべきことすべて

結論

二分探索アルゴリズムは、計算領域で広く使用されているアルゴリズムです。 これは、大小のデータセットの両方でうまく機能する、太くて正確な検索アルゴリズムです。 二分探索アルゴリズムは、実装するためのシンプルで信頼性の高いアルゴリズムです。 時間と空間の分析により、この特定の手法を使用することの利点は明らかです。

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