二分探索
半分ずつ捨てていく探索
前回の線形探索は、要素数が増えるとその分だけ比較回数も増えました。1000件なら平均500回です。これを一気に減らすのが二分探索です。ただし条件が1つあり、配列があらかじめ昇順（または降順）に並んでいなければ使えません。並んでいるという情報があるからこそ、見ていない部分をまとめて捨てられるからです。
考え方は数当てゲームと同じです。1から100までのどれかを当てるとき、まず50を聞きます。「もっと大きい」と言われたら、1から50までは二度と考えなくてよくなります。1回の質問で候補が半分になるので、100個でも7回ほどで当たります。
擬似言語で書くとこうなります
○整数型: nibunTansaku(整数型の配列: data, 整数型: target)
整数型: low, high, mid
low ← 1
high ← dataの要素数
while (low ≦ high)
mid ← (low + high) ÷ 2 の商
if (data[mid] = target)
return mid
elseif (data[mid] < target)
low ← mid + 1
else
high ← mid - 1
endif
endwhile
return -1低い側の端が low、高い側の端が high で、この2つが「まだ探す可能性が残っている範囲」を表します。mid はその真ん中です。商を取るのは、真ん中が割り切れないときに整数の位置へ落とすためです。
low と high の動きが問題の中心です
科目Bの二分探索は、ほぼ確実に low と high の途中の値を聞いてきます。ここを押さえてください。
data[mid] が target より小さいときは、mid とそれより前は全部小さいので候補から外れます。だから low を mid + 1 にします。逆に data[mid] が target より大きいときは、mid とそれより後ろが外れるので high を mid - 1 にします。どちらも mid そのものを含めない点が要です。もし low ← mid と書いてしまうと、範囲が縮まらずに無限ループになることがあります。
終了条件も大事です。low が high を追い越した瞬間、つまり low ≦ high が成り立たなくなった時点で、候補は1つも残っていません。そこで while を抜けて -1 を返します。「見つからない」がどう表現されているかを読み取れると、穴埋めで迷いません。
速さの違い
1回の比較で候補が半分になるので、要素数 n に対して比較回数はおよそ log2(n) 回です。n が 1000 なら約10回、100万でも約20回で終わります。線形探索が100万回かかるのと比べると差は歴然です。この違いを後の回で O(n) と O(log n) として整理します。
それでは、5個の配列で low と high がどう動くかを追いましょう。
課題
- 各行を実行したあとの値を入れる
- 値が変わらない変数はそのままの値を入れる
- 割り算は商だけを取り、小数は切り捨てる