この記事で分かること（目次）
1. 探索アルゴリズムとは？
データの中から目的の値を見つける方法のことです。
情報処理試験では、処理の流れや計算量（効率）、そして実装ロジックまで理解している必要があります。
2. よく出る探索法3つ
① 線形探索（Linear Search）＝ ひとつずつ調べる
- 配列の先頭から順に探す
- データが整列されていなくても使える
- 処理回数は平均で N/2 回（最悪で N 回）
- 時間計算量：O(n)
def linear_search(A, target):
for i in range(len(A)):
if A[i] == target:
return i
return -1
幼稚園児でもわかりやすく・・・
🧸 例え：おもちゃ箱の中からお気に入りのぬいぐるみを探す
- おもちゃ箱の中に、いろんなおもちゃがごちゃごちゃ入っています。
- 上から順番に「これかな？」「これじゃないな…」ってひとつずつ見ていきます。
- もし一番下にあったら、全部見ないと見つからないかもしれません。
💡 特徴：並んでなくても探せるけど、時間がかかるときもある。
② 二分探索（Binary Search）＝ 真ん中から調べる
- 整列済みデータでしか使えない
- 真ん中の値を調べ、大小で探索範囲を半分に絞る
- 時間計算量：O(log n) と高速
def binary_search(A, target):
left, right = 0, len(A)-1
while left <= right:
mid = (left + right) // 2
if A[mid] == target:
return mid
elif A[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1幼稚園児でもわかりやすく・・・
📚 例え：辞書の中から「さかな」という言葉を探す
- 辞書は「あいうえお」順に並んでいます。
- まず真ん中のページを開きます。
- 「ま」だったら、「さかな」はもっと前にある！とわかります。
- 次は前半の真ん中を開きます。
- 「か」だったら、「さかな」はもっと後にある！
- こうやって調べるページをどんどん半分に減らしていきます。
💡 特徴：並んでいるデータじゃないとできないけど、とっても早い。
③ ハッシュ探索（Hash Search）＝ 秘密の地図で一発
データの位置をハッシュ関数で計算して一発で取り出す
時間計算量：理想的にはO(1)
試験ではハッシュ表の仕組みや衝突処理（オープンアドレス法など）が問われやすい
幼稚園児でもわかりやすく・・・
🏠 例え：自分のロッカーから靴を取る
- 幼稚園には、自分だけの番号がついたロッカーがあります。
- 「5番のロッカー」ってわかっていれば、まっすぐそこへ行って靴を取れます。
- 誰かが間違えて自分のロッカーに物を入れてたら、ちょっと整理しなきゃいけません（これが“衝突処理”）。
💡 特徴：場所がわかれば一瞬で見つかるけど、番号を作るルール（ハッシュ関数）が必要。
3. 午後問題：アルゴリズムの穴埋め例
問題（例：二分探索の一部欠落）
配列 A[0] ～ A[N-1] は昇順に整列されている。
以下は、二分探索で target を探す擬似言語である。
left ← 0
right ← N - 1
(1) left ≦ right の間、繰り返す
mid ← (left + right) / 2
(2) □１
return mid
(3) □２
left ← mid + 1
else
right ← mid - 1
return -1
解答
- □１ →
A[mid] == target - □２ →
A[mid] < target
（target の方が大きければ左端を mid+1 に移動）
4. 出題傾向と解法のコツ
- 線形探索と二分探索のアルゴリズムを擬似コードで書けるようにする
- ループ条件（
<=や<）の違いに注意 - 試験では「探索回数の計算」もよく出る
例：要素数 1024 のとき、二分探索の最大回数は？
→ log₂(1024) = 10回
5. 練習のすすめ
- 小さな配列（[2, 4, 6, 8, 10] など）を使い、手計算で探索をトレース
- 午後問題過去問を紙に印刷して、空欄を書き込みながら解く
- アニメーション付きのアルゴリズム可視化ツールで動きを確認する
✍️ まとめ
- 線形探索：整列不要、遅い
- 二分探索：整列必要、高速
- ハッシュ探索：関数で直接アクセス、高速だが衝突処理が必要
- 午後問題は「空欄補完」と「処理のトレース」がカギ
「幼稚園児にもわかりやすい解説で」とChatGPTにお願いしたところ、おもちゃ箱の例など挙げてくれて、中高年にとっては大変理解しやすい説明が出てきました。
この作戦で、これからの用語にも取り組んでいこうと思います。笑