二分探索の比較回数
二分探索は範囲を半減。最悪比較回数＝⌊log2 n⌋＋1とは？
意味
二分探索は範囲を半減させていくため、比較回数はデータ数の対数に比例する。1000件は2の10乗（1024）未満なので最大10回で絞り込める。 ▍なぜ正解 二分探索は1回の比較で探索範囲がおよそ半分になる。最悪比較回数は⌊log2 n⌋＋1で、n＝1000のときlog2 1000≒9.97なので⌊9.97⌋＋1＝9＋1＝10回である。 ▍よくある間違い ＋1を忘れて9とする、線形探索の回数と取り違える。 ▍試験の狙い 二分探索の回数は「2の何乗でnを超えるか」を数える。
?応用情報技術者試験での問われ方
資料の条件で二分探索を行うとき、最悪の場合の比較回数は何回か。
答え：二分探索は範囲を半減。最悪比較回数＝⌊log2 n⌋＋1
✓覚え方
半分ずつ、1024まで10回。
「二分探索は範囲を半減。最悪比較回数＝⌊log2 n⌋＋1」を、演習で定着させる。
無料ではじめる →応用情報技術者試験の過去問を、一問ごとの8-ways解説つきで。まずは無料で。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
ukamiru 用語集 · 応用情報技術者試験