問題プレビューID: 25e19dc1基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

問 13
基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

次の記述中の [  ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 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

解答群

解説

正解は「ウ」です。 2分探索の不具合(境界条件の更新漏れ)を分析します。

  • 一般的な2分探索では low ← middle + 1 や high ← middle - 1 としますが、このコードでは low ← middle としています。
  • 例えば、要素数 2 の配列 {1, 2} で、末尾の 2 を探す場合(ウ):
    1. low=1, high=2 → middle=(1+2)÷2 = 1
    2. data[1] は 1 なので、target (2) より小さい。よって low ← middle = 1 となる。
    3. 次のループも low=1, high=2 のままであり、状態が一切変化しないため 無限ループ に陥ります。

関連問題

本文が同じ・似ている問題を表示しています