二分探索は、データの大小関係で探索範囲を狭くする方法のため、必ずデータは昇順、または降順に整列されている必要があります。

二分探索は、探索値が存在しない場合でも効率よく処理することができます。

二分探索は、データが2倍になった場合、平均探索回数は1回増えます。詳しくはスライド「二分探索の比較回数」を復習しましょう。

二分探索は次の計算式で平均比較回数と最大比較回数を求めることができます。

2^x < n(データ件数) < 2^x+1

このときの「x」が平均比較回数、「x+1」が最大比較回数です。

今回は「2¹³(8,192) < 10,000 < 2¹⁴(16,384)」なので14回です。

二分探索は次の計算式で平均比較回数と最大比較回数を求めることができます。

2^x < n(データ件数) < 2^x+1

このときの「x」が平均比較回数、「x+1」が最大比較回数です。

今回は「2⁹(512) < 1,000 < 2¹⁰(1,024)」なので9回です。