平成25年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−2
Java言語により記述された二分探索の関数 binsearch は、区間の減少のようすを
打ち出す出力命令が挿入してある。 第1引数 a
  1, 3, 4, 7, 8, 9, 12, 13, 15
に対して第2引数 x で「3」及び「14」を探したときの出力として最も適切なものはどれか。

 static int binsearch (int[] a, int x) {
  int left = 0, right = a.length - 1;
  while (left <= right) {
   System.out.printf("%d, ", right - left);
   int c = (left + right) / 2;
   if (a[c] > x) {
    right = c - 1;
   } else if (a[c] < x) {
    left = c + 1;
   } else {
    return c;
   }
  }
  return - 1;
 }

 ┌─┬────────┬──────────┐
 │ │3を探したとき │14を探したとき  │
 ├─┼────────┼──────────┤
 │@│「8, 3, 」   │「8, 3, 1, O, 」  │
 ├─┼────────┼──────────┤
 │A│「8, 3, O, 」  │「8, 3, 1, 」    │
 ├─┼────────┼──────────┤
 │B│「8, 4, 2, 」  │「8, 4, 2, 1, O, 」 │
 ├─┼────────┼──────────┤
 │C│「9, 3, 」   │「9, 4, 1, 」    │
 ├─┼────────┼──────────┤
 │D│「9, 4, 」   │「9, 4, 1, 0, 」  │
 └─┴────────┴──────────┘




【正解】 @
3を探した時のプログラムの様子を示す。
left = 0, right = 9 -1;
1回目の while (
0 <= 8) で
 System.out.printf("%d, ",
8 - 0); により 「8, 」を出力
 
c = (0 + 8) / 2 = 4
 a[
c] = a[4] = 8 により
 if (a[
4] > 3) の分岐に進んで
 
right = 4 - 1 = 3

2回目の while (
0 <= 3) で
 System.out.printf("%d, ", 3 - 0); により 「8, 3, 」を出力
 
c = (0 + 3) / 2 = 1  ・・・ 1.5は 整数型では切り捨てにより 1となる。
 a[
c] = a[1] = 3 により
 else の分岐に進んで
 return 3
にてプログラム終了。

よって、3を探した時の出力結果だけで、正解は@と判る。


念のため、14を探した時のプログラムの様子を示す。
left = 0, right = 9 -1;
1回目の while (0 <= 8) で
 System.out.printf("%d, ", 8 - 0); により 
「8, 」を出力
 c = (0 + 8) / 2 = 4
 a[c] = a[4] = 8 により
 else if (a[4] < 14) の分岐に進んで
 left = 4 + 1 = 5

2回目の while (5 <= 8) で
 System.out.printf("%d, ", 8 - 5); により 「8, 3, 」を出力
 c = (5 + 8) / 2 = 6  
・・・ 6.5は 整数型では切り捨てにより 6となる。
 a[c] = a[6] = 12 により
 else if (a[6] < 14) の分岐に進んで
 left = 6 + 1 = 7

3回目の while (7 <= 8) で
 System.out.printf("%d, ", 8 - 7); により 
「8, 3, 1, 」を出力
 c = (7 + 8) / 2 = 7
 a[c] = a[7] = 13 により
 else if (a[7] < 14) の分岐に進んで
 left = 7 + 1 = 8

4回目の while (8 <= 8) で
 System.out.printf("%d, ", 8 - 8); により 
「8, 3, 1, 0, 」を出力
 c = (8 + 8) / 2 = 8
 a[c] = a[8] = 15 により
 if (a[7] > 14) の分岐に進んで
 right = 8 - 1 = 7

5回目の while (8 <= 7) で条件が偽となり終了。


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



V−1 目次 V−3
ファーストマクロ TOPページ