基本情報技術者試験 科目B サンプル問題 問13の解説｜2分探索の関数 search が無限ループになる場合

科目B サンプル問題 問13難易度 ★★★擬似言語・while・2分探索・不具合最終更新 2026-09-22

無限ループ＝ 止まらずに回り続けること。それが起きる data はどれかを選ぶ問題です。頭の中で理屈を組み立てるより 解答群の4つを、そのまま関数に入れて動かすほうが早い ── 配列はどれも3個までで、1周か2周まわせば判断がつきます。見るのは1周まわったあとの low と high だけ。

出題

読めない記号があっても大丈夫です。次の節にまとめてあります。

○整数型: 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

この問題に出てくる記号

解答群の4つを、実際に動かして決める

〔プログラム〕はじまりの2行と、くりかえしの中

  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

※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。

while が回り続けるかどうかを決めているのは low と high の2つだけ。ですから1周まわったあとに、この2つがどうなっているかを見れば決まります。ア・イ・ウ は条件から data と target が決まるので1回入れれば済みますが、エ だけは target が指定されていないので、こちらで選んで試します。

    else
      return middle

    else
      return middle

    elseif (data[middle] ＞ target)
      high ← middle

    else
      return middle

    if (data[middle] ＜ target)
      low ← middle

ア と イ は1周目、エ は2周目に return へたどり着きました。とくに エ は target をこちらで選べてしまうので、終わる例が1つ作れた時点で、「その場合は無限ループになる」の条件にはなりません。－1 という値は while の中で一度も特別扱いされていない ── 止まるかどうかを決めているのは low と high の動き方だけです。

答え合わせ

ウ の data ＝ {5, 7}、target ＝ 7 を、最後まで押して確かめます。

止まらなくなる理由もひとことで。middle ← (low ＋ high) ÷ 2 の商 は商が切り捨てなので、low と high が隣どうしになると、middle は前側、つまり low と同じ番号に落ちます。そこで low ← middle を実行しても何も変わらない ── これがこの関数の不具合です。範囲を半分ずつ狭めて探すこのやり方を2分探索といい、low ← middle ＋ 1・high ← middle － 1 と書いてあれば、調べ終えた middle 番が必ず候補から外れるので、この止まり方は起きません。

次に読む

この問題でどこに手間取ったかで、行き先が変わります。