【にぶんたんさく】
二分探索 とは？
💡 「数当てゲーム」のアルゴリズム
📌 このページのポイント
- データがソート済みであることが前提条件
- 100万件のデータでも最大20回の比較で見つかる
- 線形探索O(n)に比べて圧倒的に高速
- IPA試験の基本アルゴリズム問題で頻出
ひよこ どういう仕組みなの？
ペンギン先生 1〜100の数当てゲームと同じ。「50より大きい？」→Yes→「75より大きい？」→No→「63より大きい？」…と半分ずつ絞る。100個のデータなら最大7回（log₂100≈7）、100万個でも最大20回で見つかる。毎回半分に絞れるから指数的に候補が減るんだよ
ひよこ 実装で注意することは？
ペンギン先生 古典的なバグとして「中間地点の計算でオーバーフロー」がある。mid = (left + right) / 2だとleft + rightが整数の上限を超えることがある。mid = left + (right - left) / 2と書くのが安全。あとoff-by-oneエラー（境界条件の1つずれ）に注意。left < rightかleft <= rightかで結果が変わるよ
ひよこ 二分探索の応用は？
ペンギン先生 ひよこ IPA試験での出題パターンは？
ペンギン先生 「n個のデータから二分探索で最大何回の比較が必要か」→⌈log₂n⌉回。「1024個のデータの二分探索の最大比較回数は？」→10回（log₂1024=10）。トレース問題（手順を追って中間値を答える）も定番。線形探索との比較で「データ数が増えた時の効率差」を問う問題もよく出るよ
まとめ：ざっくりこれだけ覚えればOK！
「二分探索」って出てきたら「ソート済みデータを半分ずつ絞り込む高速検索」と思えればだいたいOK！
📖 おまけ：英語の意味
「Binary Search」 ＝ 二分探索
💬 Binary（二つに分ける）。辞書で単語を引くとき真ん中あたりを開いて探すのと同じだよ