
二分探索の候補区間を紙に残す
解き方
『目標があれば、その位置は今の候補区間に含まれる』という条件を保ちながら読みます。中央を調べて不一致だった場合、次の区間から中央も外します。
確認問題【オリジナル】
lo ← 1
hi ← n
while lo ≦ hi
mid ← (lo + hi) ÷ 2 の整数部分
if A[mid] = target
return mid
elseif A[mid] < target
lo ← 【空欄】
else
hi ← mid − 1
endif
endwhile
return 0昇順の A=[2, 5, 9, 14, 20]から16を探します。空欄を埋めて、調べる要素番号と返り値を答えてください。
答えと解説
空欄は mid+1 です。調べる番号は3、4、5です。候補区間は[1,5]→[4,5]→[5,5]→[5,4]と変わり、最後は空になって0を返します。lo ← mid では、候補が1件のときに区間が縮まらない場合があります。