← ラボ集へ戻る
(3)イ コンピュータとプログラミング ／ アルゴリズム
🔎 二分探索の数当て
1〜100の数を1つ思い浮かべて。コンピュータが当てにいくので、大きい／小さいだけ答えて。何回で当たる？
コンピュータの予想は…
50
↓ もっと小さい
🎯 当たり！
↑ もっと大きい
質問した回数：
0
残りの候補：
100
個
やり直す
なぜ速い？
1つずつ試す線形探索は最大100回。二分探索は毎回候補を
半分
に減らすので、最大でも
log₂100 ≒ 7回
。100万個でも約20回。「半分ずつ」の威力＝対数。
ただし"並んでいる（ソート済み）"ことが前提
。