二分探索 | 基本情報技術者試験学習サイト

まず結論

二分探索はソート済み配列を前提に、中央の値と比較して探索範囲を半分に絞る高速探索です。計算量はO(log n)。n=1,000,000でも最大20回で見つかります。

なぜO(log n)なのか

      毎回範囲が半分になる：

      n=1024要素 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

      = 10回で1要素まで絞れる（log₂1024 = 10）

      線形探索なら最悪1024回。二分探索は圧倒的に速い！

二分探索の動き

ソート済み配列 [1, 3, 5, 7, 9, 11, 13, 15] から「11」を探す：

Step 1: left=0, right=7, mid=3 → a[3]=7 < 11 → 右半分を探す

↑ mid(3) 　 7 < 11 なので左半分は除外

Step 2: left=4, right=7, mid=5 → a[5]=11 = 11 → 発見！

↑ mid(5) で 11 を発見！ 2回の比較で完了

ステップ	left	right	mid	a[mid]	判断
1	0	7	3	7	7 < 11 → left = mid+1
2	4	7	5	11	11 = 11 → 発見！

擬似コード

// ソート済み配列 a[1..n] から key を二分探索手続き binarySearch(a, n, key) left ← 1 right ← n left が right 以下の間, 繰り返す mid ← (left + right) ÷ 2 // 整数除算もし a[mid] = key ならば mid を返す // 発見そうでなく, もし a[mid] < key ならば left ← mid + 1 // 右半分を探すそうでなければ right ← mid - 1 // 左半分を探すもし終わり繰り返し終わり -1 を返す // 未発見手続き終わり

🎯 試験での出方

「二分探索の前提条件」→ データがソートされている（昇順または降順）
「二分探索の計算量」→ O(log n)
left・right・midの変化をトレースする問題（科目Bで頻出）
「n=1024のとき最大何回で見つかるか」→ log₂1024 = 10回

⚠️ よくある間違い

「二分探索はソート不要」→ ✗ 必ずソート済みが前提。未ソートなら線形探索
「midは常に固定」→ ✗ midはleftとrightから毎回再計算する
「left > right になっても続ける」→ ✗ left > rightになったら未発見で終了

✍️ 確認クイズ

Q1. 二分探索を使用するための前提条件はどれか。

✅ 正解は②。二分探索は「中央と比較して半分に絞る」ため、データがソート済みであることが必須条件です。未ソートデータには使えません。

Q2. 1024要素のソート済み配列を二分探索する場合、最大何回の比較が必要か。

✅ 正解は③。log₂(1024) = 10。二分探索はO(log n)なので1024要素でも最大10回の比較で見つかります。線形探索なら最大1024回必要です。

Q3. 二分探索でa[mid] < key の場合、次の探索範囲はどこか。

✅ 正解は②。a[mid] < key のとき、目標値はmidより右にあるのでleft = mid+1として右半分を探します。a[mid] > key なら右半分 = mid-1として左半分を探します。

Q4. 二分探索を使う前提条件として必要なものはどれか。

✅ 正解は②。二分探索は中央値と比較して左右どちらかを探索するアルゴリズム。データが整列されていないと「目標値は左か右か」の判断ができないため、ソート済みであることが絶対条件です。ソート不要で使えるのは線形探索です。

Q5. 1024個の要素を持つ配列を二分探索する場合、最悪何回の比較で探索が完了するか。

✅ 正解は③。二分探索の計算量はO(log₂n)。1024=2¹⁰ なので log₂(1024)=10回。線形探索なら最悪1024回かかるところを10回で済みます。データ量が倍になっても比較回数は1回増えるだけという効率の良さが特徴です。

← 線形探索一覧バブルソート →

Sponsor Link