貴方の成長を手助けする無料ＩＴ資格スクール

2分探索において，データの個数が4倍になると，最大探索回数はどうなるか。(FE_H17春_問15)

ア　1回増える。

イ　2回増える。

ウ　約2倍になる。

エ　約4倍になる。

正解　イ

2分探索は，1回の探索(比較)で対象のデータを半分に絞り込むことができます。

仮に，元のデータの個数が1000個だったとすれば，データの個数が4倍になると4000個になります。この4000個のデータに対して2分探索を行えば，1回の探索(比較)で2000個まで減らすことができ，さらにもう1回の探索(比較)で元の1000個まで減らすことができます。

よって，データの個数が4倍になると，最大探索(比較)回数は2回増えます。

5個のデータ列を次の手順を繰り返して昇順に整列するとき，整列が完了するまでの手順の繰返し実行回数は幾つか。(IP_サンプル問題_問54)

〔整列前のデータの並び順〕
　5，1，4，3，2

〔手順〕
　(1) 1番目のデータ＞2番目のデータならば，1番目と2番目のデータを入れ替える。
　(2) 2番目のデータ＞3番目のデータならば，2番目と3番目のデータを入れ替える。
　(3) 3番目のデータ＞4番目のデータならば，3番目と4番目のデータを入れ替える。
　(4) 4番目のデータ＞5番目のデータならば，4番目と5番目のデータを入れ替える。
　(5) 一度も入替えが発生しなかったときは，整列完了とする。入替えが発生していたときは，(1)から繰り返す。

ア　1

イ　2

ウ　3

エ　4

正解　エ

基本交換法に関する問題ですが，基本交換法を知らなくても解ける問題ではあります。

とりあえず，手順に従って実行していくと，

(1) 5，1，4，3，2　→　1，5，4，3，2

(2) 1，5，4，3，2　→　1，4，5，3，2

(3) 1，4，5，3，2　→　1，4，3，5，2

(4) 1，4，3，5，2　→　1，4，3，2，5

(5) 入れ替えが発生しているので(1)から繰り返す。

(1) 1，4，3，2，5　→　1，4，3，2，5

(2) 1，4，3，2，5　→　1，3，4，2，5

以下略

このように丁寧に辿っていけば，繰返しの回数は4回であることが分かります。

頑張って辿ってみてください（＾＾；