二分検索は効率的な検索です。その複雑さの推定値は O(log2(n)) ですが、従来の逐次検索は O(n) です。これは、たとえば 1024 個の要素の配列の場合、最悪の場合、目的の要素が配列内にない場合、線形検索は 1024 個の要素すべてを処理することを意味します。 \(log_2(1024) = 10\) 要素を処理するには、二分探索で十分です。この結果は、ループの最初のステップの後、2 番目のステップの後、検索範囲が 512 要素に絞り込まれるという事実によって達成されます。最大 256 など
このアルゴリズムの欠点は、データの順序付けが必要であることと、(データ量に関係なく) 一定時間内に任意のデータ要素にアクセスできることです。したがって、このアルゴリズムは、順序付けされていない配列やリンク リストに基づくデータ構造では機能しません。
実装
さようなら (右 – 左 > 1) // 右境界線が左境界線の右側にある限り
ノースカロライナ
中央 = (左 + 右) /< /span>2; // 検索エリアの中央
if (A[middle] >= b) then
右=中央; // 右の境界線を移動
そうでない場合
左=中央; // それ以外の場合は、左の境界線を移動します
cc
場合 (A[right] == X) その後
正しい出力。
そうでない場合
出力-1;
ここで:
A - ソース配列
N - 配列サイズ
X - 目的の数値。
|