2分探索とは（全体像）
2分探索とは、並べ替え済みのデータの真ん中を見て、目的のものが前半か後半かを判断し、探す範囲を半分ずつ絞り込んでいく探し方のことだ。
辞書で単語を探すときをイメージしよう。真ん中あたりを開いて、目的の単語がそれより前か後ろかを見て、また半分にしぼる。これをくり返すと、すばやく見つかる。
ここで一番のポイント。2分探索は、データが「ソート済み（並べ替え済み）」であることが前提だ。辞書があいうえお順だからこの探し方ができるように、並んでいないとできない。「2分探索は、並んでいなくても使える万能な方法」と思い込むと誤りになる。
詳しく：前提と、速さ
ここが心臓部。2分探索のポイントを押さえよう。
2分探索のポイント
| 項目 | やさしい意味 |
|---|---|
| 探し方 | 真ん中と比べ、範囲を半分ずつ絞り込む |
| 前提 | データがソート済み（並べ替え済み）であること |
| 速さ | 線形探索より速い（O(log n)） |
| 向き | 配列向き（真ん中に一発アクセスできる） |
2分探索のすごいところは、速さだ。1回比べるごとに、探す範囲が半分になる。だから、100万件あっても、約20回の比較で見つかる。先頭から順に見る線形探索（最悪は全部調べる）より、ずっと速い。
ただし、前提としてソート済みが必要。また、真ん中に一発でアクセスできる配列向きで、つなげて持つリストは真ん中アクセスが遅いので不向きだ。
わかりやすく言い換えると
身近なたとえで整理しよう。
2分探索は、「辞書で単語を探すように、真ん中を開いて、前か後ろかでしぼっていく探し方」のイメージ。半分ずつ減るので、すぐ見つかる。
「ソート済みが前提」というのは、辞書があいうえお順に並んでいるからできること。要するに、並んでいないと、この探し方は使えない。
線形探索との違いは、「先頭から1つずつ（線形）」と「真ん中から半分ずつ（2分）」。つまり、並んでいれば2分探索のほうが速い。
試験のツボ
🔴 一番出る：2分探索の正体
①真ん中と比べ、探す範囲を半分ずつ絞り込む
②1回ごとに範囲が半分になるので、すばやく見つかる
🔴 次に出る：ソート済みが前提
①データがソート済み（並べ替え済み）であることが前提
②並んでいないと、この探し方は使えない
🟡 押さえると安定：速さと向き
①線形探索より速い（O(log n)）
②配列向き（リストは真ん中アクセスが遅く不向き）
よくある間違い
①「2分探索は、並べ替えていないデータでも使える万能な方法だ」→ ✗ 2分探索は、ソート済み（並べ替え済み）が前提。並んでいないと使えない。
②「2分探索は、線形探索より遅い」→ ✗ 2分探索は、線形探索より速い（O(log n)）。半分ずつしぼるため。
③「2分探索は、先頭から順に1つずつ調べていく方法だ」→ ✗ 先頭から順に調べるのは線形探索。2分探索は、真ん中から半分ずつしぼる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（2分探索の正体）
2分探索に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 真ん中の値と比べ、探す範囲を半分ずつ絞り込んで探す方法である
- 完成したシステムを宣伝して、より多く売るための広告活動である
解答は 3 だぱん。
2分探索は、真ん中と比べ、探す範囲を半分ずつ絞り込んで探す方法なんだぱん。辞書で単語を探すイメージだぱん。
選択肢1は給与計算、選択肢2は請求書の事務、選択肢4は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✗ | 請求書の事務の話 |
| 3 | ✓ | 半分ずつ絞り込んで探すで正しい |
| 4 | ✗ | 広告活動ではない |
オリジナル問題2（前提）
2分探索を使うための前提として、最も適切なものはどれか。
- 社員の給与を計算してから、2分探索をするのが前提だとされる
- 取引先へ請求書を郵送してから、2分探索をするのが前提とされる
- データが並べ替えられていなくても、そのまま使えるのが前提である
- データがソート済み（並べ替え済み）であることが前提になっている
解答は 4 だぱん。
2分探索は、データがソート済み（並べ替え済み）であることが前提なんだぱん。辞書があいうえお順だからできるのと同じだぱん。
選択肢1の給与、選択肢2の請求書、選択肢3の「並べ替えなくても」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算の話ではない |
| 2 | ✗ | 請求書の事務の話ではない |
| 3 | ✗ | ソート済みが前提 |
| 4 | ✓ | ソート済みが前提で正しい |
オリジナル問題3（速さ）
2分探索と線形探索の速さに関する次の記述のうち、最も適切なものはどれか。
- 2分探索は、線形探索より遅いものだとされているものである
- 2分探索は、線形探索より速い（半分ずつしぼっていくため）
- 社員の給与を計算した金額で、速さが決まるとされているものだ
- 取引先へ請求書を郵送した枚数で、速さが決まるとされている
解答は 2 だぱん。
2分探索は、線形探索より速い（半分ずつしぼるため）んだぱん。1回比べるごとに範囲が半分になるから、すぐ見つかるんだぱん。
選択肢1の「遅い」、選択肢3の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 2分探索のほうが速い |
| 2 | ✓ | 半分ずつしぼり線形より速いで正しい |
| 3 | ✗ | 給与の金額では決まらない |
| 4 | ✗ | 請求書の枚数では決まらない |
まとめ
押さえどころ
- 🔴 2分探索 ＝ 並べ替え済みのデータを、真ん中と比べ、範囲を半分ずつ絞り込んで探す方法。
- 🔴 ソート済みが前提 ＝ データが並べ替え済みでないと使えない。
- 🟡 速さと向き ＝ 線形探索より速い（O(log n)）。配列向き（リストは真ん中アクセスが遅く不向き）。
次に学ぶ
- 線形探索 ── 先頭から順に探す方法。2分探索と比べると、速さと前提の違いが分かる。
- ソート ── データを並べ替える処理。2分探索を使う前の準備になる。
執筆: SikakuQuest編集部