問 題
右に示す C 言語の関数 binary search は要素が昇順に並べられた整数配列 a から配列に含まれる指定値を 2 分探索法で検索するプログラムである。この関数の引数 v は検索対象となる指定値left right は、検索範囲の左端、右端のインデックスを表す。
この関数のアルゴリズムは以下のように構成されている。
1) 指定値を配列中の与えられた範囲の中央の値と比較し一致していれば中央のインデックスを返して停止する。
2) 指定値の方が小さければ指定値は中央点よりも左にあることが分かるので中央点の左側部分に対して再帰的に検索を行う。
3) 指定値の方が大きければ指定値は中央点よりも右にあることが分かるので中央点の右側部分に対して再帰的に検索を行う。
図は長さ10の配列に対して関数 binary searchを適用する際のleft とright の様子を表す。
関数 binary search に長さ 95 の配列を与え配列中の値を検索することを考える。この関数中で用いられる比較関数 cmp は最大何回呼び出されるか。ただし cmp は二つの引数をとり両者が等しい場合に 0 を第１引数の方が小さい場合に 1 を第 1 引数の方が大きい場合に－1 をそれぞれ返す関数とする。
1. 5
2. 7
3. 21
4. 22
5. 23
解 説
２分探索法は、ソート済の配列に対する探索法です。 n 個のデータ数に対し、O 記法による時間計算量が O(log2n) であることが知られています。データ数が増えても計算時間の増加が緩やかというイメージです。また、cmp とは compare 「比較する」を短縮した関数名と考えられます。
長さ 95 の配列に、データがソート済みということなので、1,3,5,,,,189 という、初めが１で２ずつ増えていくデータ列を考えてみます。小さい方から、配列 a[0],a[1],,,a[94] に代入されているとします。すなわち、a[0] = 1,a[1] = 3,,,a[94] = 189 です。left = 0, right = 94 です。
プログラム通りに実行してみます。すると、x = (0 + 94)/2 = 47 となります。a[47] = 93 のはずです。指定値が 93 より小さければ、左部分を検索なので、left = 0 で、right に x-1 を、つまり right = 46 として、また x を計算します。これにより、探索するデータ数は半分になりました。
以下、半分ずつにデータをへらすことができるので、95 → 47 → 23 → 11 → 5 → 2 → 1 と、探索するデータ数は減っていきます。最後まで見つからなかったとしても、探索はせいぜい 7 回とわかります。
※半分ずつ減っていくから、データ数 26 < 95 < 27 で 7 回とスパッと出しても、もちろんOKです。
以上より、正解は 2 です。
コメント