探す範囲を絞る
- 線形探索で一致までの比較を数える
- 整列済み配列を中央との大小で絞る
- 整列の前提と一般的な計算量を区別する
点線のことばを押すと、意味と使い方を調べられます。
表示・保存
このページの目次 3節・復習と3問
- 1説明を読む
- 2復習する
- 3問題を解く
- 4次へ進む
1線形探索は一つずつ調べる
探索は目的の値や条件に合うデータを見つける処理です。線形探索法は先頭などから一つずつ比較します。未整列でも使えます。
配列[8,3,9,2]から9を探すなら、8は違う、3は違う、9は一致の3回です。見つからない場合は全要素を調べます。最悪時や平均的な比較回数は一般に要素数に比例しますが、先頭なら1回です。
8≠9
3≠9
9＝9で発見
数値は学習用の例。
22分探索は整列済みの中央を見る
2分探索法は値が昇順又は降順に整列した配列で、中央と比較し探索範囲を半分ずつ絞ります。昇順[2,4,6,8,10,12,14]から12を探すなら、中央8より大きいので右半分[10,12,14]、その中央12で見つかります。
順序がなければ中央より大きい値が左右どちらにもあり得て、半分を除外できません。整列が必要なのは2分探索で、線形探索に必須ではありません。
値の大小で左右を選べるのは、探索対象が整列済みだからです。この例では中央8と12の2回の比較で見つかります。
3一般的な増え方と今回の回数を分ける
2分探索では候補が半分ずつになるため、大きな配列では線形探索より少ない比較で済みやすくなります。候補数8→4→2→1のように減ります。
ただし探す値が先頭なら線形探索は1回です。「同じ配列ならどの値でも必ず2分探索の方が少ない」とは限りません。整列のための前処理、更新頻度、探索回数を含めて方法を選びます。
ハルとビットで、使い方を確かめよう
半分ずつならいつも最速？
先頭で見つかる線形探索は1回だよ。今回の回数と一般的な効率を分けよう。
復習
このレッスンを振り返ろう
一致した後の要素も比べる？
答え方と、確認するポイント
この探索は一致で止めるので比べません。
中央の値を除いた後、次にどこを見る？
答え方と、確認するポイント
残した候補範囲の中央です。
どんな値でも2分探索の方が少ない回数？
答え方と、確認するポイント
いいえ。先頭なら線形探索が1回です。一般的な増え方とは分けます。
問題で確かめる
実際の問題に挑戦しよう
IPA（独立行政法人 情報処理推進機構）公開過去問1問、入門の確認問題2問で、この範囲の考え方を使います。答えを選んだら、正解の理由とほかの選択肢の違いも確かめましょう。
ヒントを見る
線形探索は一つずつ調べるで、条件と手順を確認しよう。
オリジナル入門問題 · シラバス 6.5
公開問題・原図の著作権はIPAにあります。表記・表の配置を整えています。解説は当サイト独自のものです。
3問中0問の答えと解説を確認しました。選んだ答えの理由も確かめてから、次へ進みましょう。
出典・参考資料を確認する
学習範囲：IPA シラバス Ver.6.5 ↗ 項目37。身近な例・会話・図解・確認問題は当サイトのオリジナルです。
学習範囲と参考資料
シラバスは学習範囲の根拠です。説明・図の数値・身近な事例は学習用に作成しています。2026年9月14日確認。