平成16年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−5
C言語の関数 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 が配列に
含まれるとした場合、比較回数の最小値と最大値を次の中から選べ。

@ 最小値 1回、最大値 3回  A 最小値 1回、最大値 7回
B 最小値 2回、最大値 6回  C 最小値 2回、最大値 7回
D 最小値 2回、最大値 8回




【正解】 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回となる。

EXCELのマクロのご相談なら ファーストマクロ 



W−4 目次 W−6
ファーストマクロ TOPページ