1
線形探索
探索配列の先頭から順に1つずつ target と比べていく、もっとも基本的な探索です。整列されていない配列でも使えるのが強みで、見つからなかったときは pos が -1 のまま残ります。最悪の比較回数は要素数と同じ n 回です。
解説とシミュレーターを見る重要アルゴリズム解説
共通テスト「情報Ⅰ」第3問の学習に向けて、押さえておきたい7つのアルゴリズムを一覧にまとめました。 それぞれの要約を読んで、気になるものは詳細ページへ進んでください。詳細ページでは、値を自分で変えながら1ステップずつ動きを確認できるシミュレーターと、擬似言語・Python・JavaScript のコード、出題ポイントまで解説しています。
2
二分探索
探索整列済みの配列の中央を調べ、大小の判定で探索範囲を毎回半分に絞ります。low・high・mid の更新と「左右どちらを捨てるか」が要点です。整列済みでないと使えない代わりに、1000個でも約10回で見つかります。
解説とシミュレーターを見る
3
交換法（バブルソート）
整列隣り合う2つの値を比べ、順序が逆なら交換していく整列です。1回のパスごとに大きい値が右端へ確定していきます。交換が起きた回数を数えさせる問題が出やすいところです。
解説とシミュレーターを見る
4
選択法（選択ソート）
整列未整列部分から最小値の位置を探し、その位置と先頭側を1回だけ交換する整列です。最小値の位置 min_pos を覚えておく流れが要点で、1パスで1個ずつ確定します。
解説とシミュレーターを見る
5
モンテカルロ法
シミュレーション乱数で試行を大量に繰り返し、条件を満たした割合から答えを近似します。正方形と円を使って円周率を求める例が定番です。厳密な解ではなく近似で、試行回数を増やすほど値が安定します。
解説とシミュレーターを見る
6
待ち行列シミュレーション
シミュレーション到着時刻・開始時刻・終了時刻・待ち時間を、1人ずつ順番に更新していきます。「開始時刻 = 最大値(到着時刻, 前の客の終了時刻)」が中心の式で、ここを押さえれば表を埋められます。
解説とシミュレーターを見る
7
運動シミュレーション
シミュレーション位置と速度を、決められた順番で繰り返し更新していきます。更新の順番を入れ替えると結果が変わる点が最大の注意点で、終了条件と表示のタイミングもよく問われます。
解説とシミュレーターを見るCOMPARE
どれを使うか：見分け方のまとめ
7つのアルゴリズムは、はたらきで3つのグループに分かれます。 問題文から「どのアルゴリズムの話か」を見抜けると、聞かれていることが一気に見えるようになります。
探索：目的の値を見つける
| 項目 | 線形探索 | 二分探索 |
|---|---|---|
| 前提 | なし（並びは自由） | 整列済みでないと使えない |
| 進め方 | 先頭から1つずつ比べる | 中央と比べて半分を捨てる |
| 最悪の比較回数 | n 回 | 約 log2(n) + 1 回 |
| 1000個のとき | 最悪1000回 | 約10回 |
| 覚える変数 | i、pos | low、high、mid、pos |
選び方：1回だけ探すなら整列の手間がいらない線形探索、同じデータを何度も探すなら整列してから二分探索が有利です。 「整列にかかる手間」と「探索を何回行うか」を比べる、という考え方が問われます。
整列：小さい順に並べ替える
| 項目 | 交換法 | 選択法 |
|---|---|---|
| やること | 隣どうしを比べて逆なら交換 | 最小値を探して1回だけ交換 |
| 確定する向き | 右端（最大値）から | 左端（最小値）から |
| 比較回数 | n(n-1)/2 回 | n(n-1)/2 回（同じ） |
| 交換回数（最大） | n(n-1)/2 回 | n - 1 回 |
| 覚える変数 | なし（その場で交換） | min_pos（最小値の位置） |
見分け方：コードに min_pos のような「位置を覚える変数」があれば選択法、
隣どうし（Nums[j] と Nums[j + 1]）を比べていれば交換法です。
どちらも計算量は O(n²) で、交換が少ないほうが必ず速いとは言えません。
シミュレーション：現実の動きを数で追う
| 種類 | 中心になる考え方 | 答えの性質 |
|---|---|---|
| モンテカルロ法 | 乱数で試行し、条件を満たす割合を数える | 近似（毎回変わる） |
| 待ち行列 | 開始 = 最大値(到着, 前の人の終了) | 計算どおりの値 |
| 運動 | 位置と速度を決めた順に更新する | 更新順で変わる |
シミュレーションは「1回の繰り返しで何をするか」を1行ずつ追えるかが勝負です。 乱数が出てきたらモンテカルロ法、時刻の列が出てきたら待ち行列、位置と速度が出てきたら運動、と見当をつけて表を書き始めましょう。
共通する学習法：どのアルゴリズムでも、紙に変数の欄を作って1行ずつ埋めるのがいちばん確実です。
各詳細ページのシミュレーターは、その作業を画面上で再現したものです。
まず自分で予測し、そのあと答え合わせに使ってください。