技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�W−５

Ｃ言語の関数 bsearch を以下のように定義する。渡される引数は、ソートされた整数の配列、その要素数、および、探索すべき値である。配列内を探して見つかった場合は1を、見つからなかった場合は0を返す。

int b search (int a[], int N, int x){
　int L, R, m;
　L = 0 ; R = N - 1;
　while (L < R){
　　m = (L + R) / 2;
　　if (x < a[m]) R = m - 1;
　　else if (x > a[m]) L = m + 1;
　　else return 1;
　}
　if(x == a[m]) return 1; else return 0;
}

この関数を呼び出した場合、引数 x と配列の要素を比較した回数の総和は、配列の内容と引数 x の値に応じて様々である。Nが8であり、x が配列に含まれるとした場合、比較回数の最小値と最大値を次の中から選べ。

---

正解

�C

---

解説

※このプログラムでは、正しく2分検索はできない。
最後のステップが
if(x == a[m]) return 1; else return 0; ではなく
if(x == a[L]) return 1; else return 0; なら正しく動作する。
以下、正しい動作のプログラムを前提に、
a[0] = 0, a[1] = 1, ・・・ a[7] = 7 が入っているとして
探査すべき値で比較回数を調べる。

x ＝ 0の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(0 < a[3]) R = 3 - 1 = 2　　・・・�@
L=0, R=2 で2回目のループ
　m = (0 + 2) / 2 = 1
　if(0 < a[1]) R = 1 - 1 = 0　　・・・�A
L=0, R=0でループを抜ける
　if(0 == a[0]) return 1;　　　・・・�B

x ＝ 1の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(1 < a[3]) R = 3 - 1 = 2　　・・・�@
L=0, R=2 で2回目のループ
　m = (0 + 2) / 2 = 1
　if(1 < a[1]) 　　　　　　　　　・・・�A
　else if (1 > a[1]) 　　　　　　・・・�B
　else return 1;

x ＝ 2の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(2 < a[3]) R = 3 - 1 = 2　　　・・・�@
L=0, R=2 で2回目のループ
　m = (0 + 2) / 2 = 1
　if(2 < a[1]) 　　　　　　　　　　・・・�A
　else if (2 > a[1]) L = 1 + 1 = 2　・・・�B
L=2, R=2でループを抜ける
　if(2 == a[2]) return 1;　　　　・・・�C

x ＝ 3の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(3 < a[3]) 　　　・・・�@
　else if (3 > a[3]) 　・・・�A
　else return 1;

x ＝ 4の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(4 < a[3]) 　　　　　　　　　　・・・�@
　else if (4 > a[3]) L = 3 + 1 = 4　　・・・�A
L=4, R=7 で2回目のループ
　m = (4 + 7) / 2 = 5
　if(4 < a[5]) R = 5 -1 = 4　　・・・�B
L=4, R=4でループを抜ける
　if(4 == a[4]) return 1;　　　　・・・�C

x ＝ 5の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(5 < a[3]) 　　　　　　　　　　・・・�@
　else if (5 > a[3]) L = 3 + 1 = 4　　・・・�A
L=4, R=7 で2回目のループ
　m = (4 + 7) / 2 = 5
　if(5 < a[5]) 　　　　　　・・・�B
　else if (5 > a[5]) 　　・・・�C
　else return 1;

x ＝ 6の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(6 < a[3]) 　　　　　　　　　　・・・�@
　else if (6 > a[3]) L = 3 + 1 = 4　　・・・�A
L=4, R=7 で2回目のループ
　m = (4 + 7) / 2 = 5
　if(6 < a[5]) 　　　　　　　　　　　・・・�B
　else if (6 > a[5]) L = 5 + 1 = 6　　・・・�C
L=6, R=7 で3回目のループ
　m = (6 + 7) / 2 = 6
　if(6 < a[6]) 　　　　　　・・・�D
　else if (6 > a[6])　　　・・・�E
　else return 1;

x ＝ 7の時
L=0, R=7 で1回目のループ
　m = (0 + 7) / 2 = 3
　if(7 < a[3]) 　　　　　　　　　　・・・�@
　else if (7 > a[3]) L = 3 + 1 = 4　　・・・�A
L=4, R=7 で2回目のループ
　m = (4 + 7) / 2 = 5
　if(7 < a[5]) 　　　　　　　　　　　　　　・・・�B
　else if (7 > a[5]) L = 5 + 1 = 6　　・・・�C
L=6, R=7 で3回目のループ
　m = (6 + 7) / 2 = 6
　if(7 < a[6]) 　　　　　　　　　　　　・・・�D
　else if (7 > a[6]) = 6 + 1 = 7　　・・・�E
L=7, R=7でループを抜ける
　if(7 == a[7]) return 1;　　　　・・・�F

従って最小値は2回、最大値は7回となる。

�W−４

目次

�W−６

---