問題
次の二分探索プログラムの空欄[ ]に入る式はどれか。arr（ソート済み）からtargetを探す。
○ 整数型: binarySearch(整数型の配列: arr, 整数型: target)
整数型: low ← 0
整数型: high ← arr の要素数 − 1
while (low ≦ high)
整数型: mid ← [ ]
if (arr[mid] = target)
return mid
elseif (arr[mid] < target)
low ← mid + 1
else
high ← mid − 1
endif
endwhile
return -1
選択肢
- 1low + high
- 2(low + high) / 2
- 3low * high
- 4high − low
正解
2. (low + high) / 2
詳しい解説を見る解説を閉じる
解説
二分探索は、ソート済み配列の探索範囲の中央の値と目的の値を比較し、範囲を半分に絞り込む操作を繰り返すアルゴリズムである。中央の添字はmid=(low+high)/2（整数除算）で求める。例えばlow=0、high=9ならmid=(0+9)/2=4となり、arr[4]とtargetの大小関係に応じてlow=mid+1またはhigh=mid−1で探索範囲を半分にしていく。low+highは中央ではなく範囲を超えた位置を指し得る（low=0、high=9なら9で末尾になる等）。low*highやhigh−lowは中央の位置を表す式ではないため誤りである。二分探索は1回の比較で範囲が半分になるため計算量はO(log n)であり、線形探索のO(n)との対比、および「ソート済みであることが前提」という適用条件が頻出ポイントである。
一問一答
科目A 180問+科目B 60問