平成26年度 秋期 午前 問6

✓ これが正解ア2 分探索するデータ列は整列されている必要がある。

解説

真ん中を見て半分を捨てるので並びが前提です。

2 分探索は、データの真ん中を見て、探している値がそれより大きいか小さいかで残りの半分を捨て、これを繰り返して目的の値にたどり着く手順です。ここで押さえておきたいことが三つあります。一つ目は前提で、真ん中を見て片側を捨てられるのは、データが大小の順に並んでいるからです。並んでいなければ、真ん中と比べても、どちら側を外せるかが決まりません。二つ目は手順で、見に行く場所は真ん中であって端ではありません。三つ目は手間の増え方で、範囲が毎回半分になるため、比較の回数はデータの個数の対数に比例して増えます。判定の軸は、この三つのどれに触れているかという一点で、正解にあたるのは一つ目の前提を述べたものです。

ほかの選択肢はなぜ違うのか

• イ2 分探索は線形探索よりも常に速く探索で…：言い切りの形になっているところが誤りです。データの個数がごく少ないときや、探している値がたまたま先頭にあるときは、順に見ていくやり方のほうが早く終わります。
• ウ2 分探索は探索をデータ列の先頭から開始…：先頭から順に見ていくのは線形探索のやり方です。範囲の中央を起点にして半分ずつ絞り込むという手順そのものと食い違います。
• エn 個のデータの 2 分探索に要する比較…：比較の回数の増え方を、個数と対数を掛け合わせた量としています。これは並べ替えの手間の目安として知られる量で、絞り込みの回数の増え方より大きくなります。