日本語

探索：線形探索と二分探索

中学校コンピューターサイエンスソート済みの一意な偶数整数配列に対する完全一致検索（0始まりのインデックス）

パスを使ってこの実験を利用する

パスがあれば、授業用のプレゼンテーションモードを含む、サイト上のすべてのシミュレーションを利用できます。以下の指導用ノートは、どなたでも無料でご覧いただけます。

パスを見るすでにパスをお持ちの方

一度限りのお支払いで、サブスクリプションはありません。

この実験について

線形探索と二分探索を並べて、同じ値を探します。各ステップでは、まだ終了していない各アルゴリズムで比較を1回ずつ行います。二分探索は残っている整列済み区間の中央を調べ、線形探索は1つずつ位置を進めます。奇数の値を選ぶと、どちらのアルゴリズムも一致する値を見つけずに終了する様子を確認できます。

学習目標

  • 二分探索で候補区間と中間位置を追跡する
  • 線形探索と二分探索の比較回数を比べる
  • 二分探索に整列済みデータが必要な理由と、見つからない値をどう扱うかを説明する

使い方

  1. 1既定の配列で32を探し、比較を1回ずつ進めます。
  2. 2二分探索が終了するタイミングを確認してから、線形探索が終了するまで続けます。
  3. 331などの奇数の値を選びます。二分探索で候補区間が空になる様子を確認します。
  4. 4配列の長さを変更して、最後の値を探します。最悪の場合の上限を比べます。

モデル

二分探索における、両端のインデックスを含む場合の中間位置
二分探索での値の比較回数の上限
ここに示した線形探索の最悪の場合の比較回数

前提条件

  • 配列には、昇順に並んだ重複のない偶数の整数 2、4、…、2n が含まれています。インデックスは 0 から始まります。
  • 値の比較とは、対象の値との 3 方向比較を 1 回行うことです。インデックスの計算やループ条件の確認は数えません。
  • 線形探索では、対象の値がない場合、配列全体を走査します。並べ替え済みであることを利用した早期終了の最適化は行いません。
  • 各行は、その探索が完了した状態のまま表示され、もう一方の探索が続きます。現在の候補範囲は、現在の比較結果が反映される前に表示されます。

授業で試してみましょう

  1. Q1比較を 1 回行うだけで、二分探索では残りの位置の半分を除外できるのはなぜですか？
  2. Q232 個の値がある配列で、最後の値を見つけるには、それぞれの方法で比較が何回必要ですか？
  3. Q3ソートされていない配列に同じ中点のルールを適用すると、何がうまくいかなくなりますか？

よくある質問

二分探索が奇数の対象値を見つけられないのはなぜですか？

配列の各要素はすべて偶数です。奇数の対象値が一致することはないため、候補範囲は最終的に空になり、アルゴリズムは見つからなかったと報告します。

一方の行の動きが止まったのはなぜですか？

その探索はすでに終了しています。ステップを進めると、もう一方のアルゴリズムが続行され、両者の比較コストの合計を比べられます。