科目B
基本情報技術者試験 科目B サンプル問題セット（2022年12月公表） 問13
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 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
答えを選ぶ
出典：基本情報技術者試験 科目B サンプル問題セット（2022年12月公表） 問13（問題文は IPA の公開問題。図・数式・下線などはテキストに直して掲載。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ウ
覚える知識
2分探索の範囲更新(middle±1)
2分探索では探索範囲を low←middle＋1 / high←middle−1 と、中央を除いて縮める。中央を残すと範囲が縮まらず、止まらなくなることがある。
この問題で必要なこと
low←middle（＋1 がない）なので、範囲が縮まらないことがある。要素数 2 で target が末尾のとき、low=1・high=2 で middle=1。data[1]＜target なので low=1 のままになり、無限ループする。正解はウ。
ひっかけ
先頭要素が target のとき（イ）は最初の middle=1 で見つかって終わる。要素数 1（ア）も即座に見つかる。−1 を含む（エ）は戻り値との混同を誘うだけで、ループとは関係ない。