2,000個の相違なる要素が、キーの昇順に整列された票がある。外部から入力したキーによってこの表を二分探索して、該当するキーの要素を取り出す。該当するキーがかならず表中にあることがわかっている時、キーの比較回数は最大何回か。
- ア： ９
- イ： １０
- ウ： １１
- エ： １２
2,000個の相違なる要素が、キーの昇順に整列された票がある。外部から入力したキーによってこの表を二分探索して、該当するキーの要素を取り出す。該当するキーがかならず表中にあることがわかっている時、キーの比較回数は最大何回か。
正解： ウ
解説：
二分探索法は、対象データが探索範囲の前方にあるか、後方にあるかで、探索範囲を半分にすることを繰り返すので、元の2000個のデータを何回2分割できるか数えると、11回となる。
また、二分探索法の最大比較回数は、「 ( log2n ) ＋ 1」で求められる。ただ、これはデータが見つからないかもしれない場合に、分割した要素が1つになった後も比較が必要なため、＋１回されている。
今回はかならず表中にあるので、log2 2000 を求めればよい。
log2 2000 ＝ 10.965・・・なので、切り上げて11回であることが求められる。
なお、log2 2000 の計算は関数電卓が必要だが、「210＝1024」を覚えておけば、「log2 1024＝10」が分かるので、以下のように求めることも出来る。
10 ＝log2 1024＜log2 2000＜log2 2048＝11