うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問13

2分探索 ・ 無限ループ ・ 不具合の特定

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 search は,引数 data で指定された配列に,引数 target で指定された値が含まれていればその要素番号を返し,含まれていなければ[ ]-1 を返す。data は昇順に整列されており,値に重複はない。
関数 search には不具合がある。例えば,data の[ ]場合は,無限ループになる。

○整数型: search(整数型の配列: data, 整数型: target)
  整数型: low, high, middle
  low ← 1
  high ← dataの要素数
  while (low ≦ high)
    middle ← (low + high) ÷ 2 の商
    if (data[middle] < target)
      low ← middle
    elseif (data[middle] > target)
      high ← middle
    else
      return middle
    endif
  endwhile
  return -1
a
ア{5}, 5
イ{3, 8}, 3
ウ{3, 8}, 8
エ{-1, 3, 8}, -1

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問13

正解と解説を見る

正解:ウ

ポイント:2分探索で low ← middle(+1 しない)にすると、範囲が縮まらず無限ループになる場合がある。

このプログラムは、low ← middle、high ← middle となっていて、正しい2分探索の low ← middle + 1、high ← middle - 1 になっていません。そのため、範囲が縮まらない場合があります。
ウ {3, 8} で 8 を探す:low=1、high=2、middle=(1+2)÷2 の商=1。data[1]=3 < 8 なので low ← 1。low も high も変わらず、同じことを永遠に繰り返します(ウ)。
ア {5} で 5:middle=1 ですぐ見つかります。
イ {3, 8} で 3:middle=1 ですぐ見つかります。
エ {-1, 3, 8} で -1:middle=2、3 > -1 なので high ← 2。次に middle=1 で見つかり 1 を返します。-1 が要素にあっても、戻り値の -1(見つからない)と混同するだけで、無限ループにはなりません。
トレースすると、ウだけ low・high・middle の値が変わらないまま回り続けるのが見えます。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

サイトで、1行ずつ動かして読む →