問題
次の二分探索プログラムの空欄[ ]に入る式はどれか。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
選択肢
- 1ア low + high
- 2イ (low + high) / 2
- 3ウ low * high
- 4エ high − 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問