さがす——半分に切る
辞書の引き方に、戻る
前のレッスンの最後に、種をまいておきました。もし数列が小さい順にそろっていたら——まんなかを1回見るだけで、半分を捨てられるはずです。
これは、最初のレッスンの辞書の引き方そのものです。「みどり」を引くとき、まんなかへんを開いて「は行か——行きすぎ」と戻る。あのとき捨てているのは1ページではなく、開いたページから手前ぜんぶです。
なぜそんな大胆なことができるのでしょうか。辞書のことばが五十音順にそろっているからです。「は行」のページより手前に「みどり」はない——見もしないで、そう言い切れます。
まんなかとくらべて、半分にしぼる
この引き方を、曖昧さのない手順にします。
- 残っている範囲の、まんなかの数と探し物をくらべる
- 同じなら、見つかり。終わり
- まんなかの数が探し物より小さければ、探し物は右側にしかいない——左半分をまとめて捨てる
- 大きければ、右半分をまとめて捨てる
- 範囲がなくなるまで、くりかえす
「半分に切ってさがす」——**二分探索（にぶんたんさく）**と呼びます。前のレッスンと同じ数列で、68をさがしてみてください。
まんなかの 30 は 68 より小さい——右半分にしぼる
2回で見つかりました。薄くなったセルが「捨てた範囲」です。1歩目でまんなかの30とくらべ、「68より小さい」のひとことで、30より左の4個は一度も見られないまま消えました。
探し物を打ちかえて、遊んでみてください。この数列では、どの数をさがしても4回を超えません。どこにもない数（たとえば50）でも4回で「ありません」と言い切れます——範囲がなくなったことが、そのまま「居場所がどこにもない」の証明になるからです。
並走させてみる
ほんとうに速いのか、前のレッスンの「まっすぐさがす」と同じ土俵で競わせましょう。探し物は91——まっすぐ派にとって最悪の、いちばん奥の数です。
1番目は 3。91 ではない
まんなかの 30 は 91 より小さい——右半分にしぼる
まっすぐ10回、半分切り4回。ただし探し物を3に打ちかえると、まっすぐ派が1回対3回で勝ちます——運くらべなら、負けることもあるのです。それでも前のレッスンで決めたとおり最悪の場合でくらべれば、10回対4回です。
倍にしても、1回増えるだけ
10個で最大4回なら、1,000個ではどうでしょう。まっすぐなら最悪1,000回のところ、半分切りは最大10回です。
からくりはこうです。1回くらべるたびに残りが半分になるので、数列の長さを倍にしても、最悪の回数は1回増えるだけ。1,000個が2,000個になっても、10回が11回になるだけです。
だから100万個でも、約20回で済みます。この信じがたいほど平らなかたちには**対数（log）**という名前がついています。いまは名前だけで十分です——かたちどうしの本格的な力くらべは、あとのレッスンでやります。
この速さは、何で買ったのか
ここまでが、よい知らせでした。ここからが、このレッスンでいちばん大事な話です。
二分探索の1歩は、「まんなかより左はぜんぶ小さい」という約束を当てにして、見もせずに半分を捨てています。では、約束が破れていたら——そろっていない数列にこの手順をかけたら、何が起きるでしょうか。実験室は、止めてくれません。
同じ10個の数をバラバラにならべた列で、42をさがしてみてください。42は、列の先頭に見えています。
まんなかの 57 は 42 より大きい——左半分にしぼる
3回くらべて、「42はありません」。手順が、嘘をつきました。1歩目で57とくらべて「42は左にいるはず」と右半分を捨てた——その判断が正しいのは、そろっている列の上だけです。
42は目の前の先頭にいたのに、手順は最後までそこを見ませんでした。さらにたちが悪いことに、嘘は毎回ではありません。同じ列で8をさがすと2回で正しく見つかります——切る方向が、たまたま当たっただけなのですが。
⟡ よりみち：人間は、まんなかを開かない
辞書で「みどり」を引くとき、あなたはたぶん後ろ寄りを開きます。「み」は五十音の終わりのほうだと知っているからです。この勘を手順にしたもの（補間探索）もあって、当たれば二分探索より速い——ただし「ことばの散らばり方」への信頼を、さらに上乗せして買う速さです。辞書のたとえは、ここから先は二分探索と少しずれます。
✎ 演習：嘘をつかれる数、つかれない数
実験室のバラバラの列はそのままで、探し物を打ちかえながら調べてください。
- 列の中にあるのに「ありません」と言われる数を、42のほかに1つ見つける
- 正しく見つかる数を1つ見つける
- その数が正しく見つかった理由を、場面を1歩ずつ見て説明する
ヒント1（考え方）
この列では、1歩目はかならず5番目の57とくらべます。「57より小さいから左へ」という判断が、結果として正しい方向になる数は、どれでしょう。
こたえ
あるのに「ありません」と言われるのは、42のほかに3・14・21・30・75・91。正しく見つかるのは8・57・68の3つだけです。57はまんなかにいるので1回で当たります。8は「57より小さい→左へ」と切った先のまんなかが、たまたま8だったから——方向の判断がぜんぶ偶然当たった、というだけです。10個中7個に嘘をつく手順が、3個ではちゃんと動く。数回ためして通ったくらいでは、この壊れ方は見つかりません。
このレッスンで分かったこと
- 半分に切ってさがす（二分探索）：まんなかとくらべて、半分をまとめて捨てる。10個なら最大4回
- 長さを倍にしても、最悪の回数は1回増えるだけ。100万個でも約20回——このかたちの名前は対数
- そろっていない列にかけると、あるものを「ありません」と言うことがある。しかも毎回ではない
- 速さは、「そろっている」という前提への信頼で買っている