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;
}
┌─┬────────┬──────────┐
│ │３を探したとき │１４を探したとき │
├─┼────────┼──────────┤
│①│「8, 3, 」 │「8, 3, 1, O, 」 │
├─┼────────┼──────────┤
│②│「8, 3, O, 」 │「8, 3, 1, 」 │
├─┼────────┼──────────┤
│③│「8, 4, 2, 」 │「8, 4, 2, 1, O, 」 │
├─┼────────┼──────────┤
│④│「9, 3, 」 │「9, 4, 1, 」 │
├─┼────────┼──────────┤
│⑤│「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) で条件が偽となり終了。
| Ⅲ－１ | 目次 | Ⅲ－３ |