二分探索
この用語のポイント
データの探し方だよ
「真ん中から半分に分けて条件に合わない方を消す」を何回もやることで、候補を絞り込んでいくよ
データが順番に並んでいるときに使えるよ
簡単に書くよ
二分探索（読：ニブンタンサク 英：binary search）とは
「半分ずつ消去法」なデータの探し方。
もう少し具体的に書くと
データが順番に並んでいる前提で、まずは真ん中のデータを取り出して「探しているデータは、これより大きい？」を確認する。もし「大きいよ！」だったら、真ん中のデータとそれより小さいデータを全部消す（「小さいよ！」だったら大きい方を消す）。残ったデータの中から真ん中のデータを取り出して「探しているデータは、これより大きい？」を確認する。……というのを繰り返すことで、条件に合わないデータを半分ずつ消していって、目的のデータを見つける やり方
です。
詳しく書くよ
頑張って一息で説明すると、データが順番に並んでいる前提で
１．真ん中のデータを取り出す
２．探しているデータと１で取り出したデータを比較する
３－１．「探しているデータと１で取り出したデータが同じ」だったら、それが探しているデータ
３－２．「探しているデータの方が１で取り出したデータよりも大きい」だったら１で取り出したデータとそれよりも小さいデータを全部消す
３－３．「探しているデータの方が１で取り出したデータよりも小さい」だったら１で取り出したデータとそれよりも大きいデータを全部消す
４．残っているデータの中から真ん中のデータを取り出す
を繰り返すことで目的のデータを見つける やり方
が「二分探索」です。
「バイナリサーチ」とも呼ばれます。
……と言葉で説明されてもサッパリ分かりませんよね。
大丈夫です。
例を挙げて説明します。
例えば、そうですね。
ここに「1」から「9」までの数字が小さい順に並んだ状態であったとしましょう。
この中から二分探索で「8」を探すことにします。
まずは真ん中の数字を取り出します。
「5」ですね。
次に、探している数字が真ん中の数字よりも大きいか小さいかを確認します。
１．探している数字は「5」だよ
２．探している数字は「5」より大きいよ
３．探している数字は「5」より小さいよ
のどれかを確認するわけです。
今回、探しているのは「8」です。
ということは
２．探している数字は「5」より大きいよ
になりますね。
探している数字が「5」より大きいと分かった時点で「1」「2」「3」「4」「5」は消せます。
「5」以下の数字は、探している数字ではないからです。
次に、残った数字の中から、さっきと同じように真ん中の数字を取り出します。
残っている数字は「6」「7」「8」「9」の4つです。
真ん中の数字は「7」か「8」ですね。
とりあえず今回は「7」ということにしておきましょうか。
次に、さっきと同じように、探している数字が真ん中の数字よりも大きいか小さいかを確認します。
１．探している数字は「7」だよ
２．探している数字は「7」より大きいよ
３．探している数字は「7」より小さいよ
のどれかを確認するわけです。
今回、探しているのは「8」です。
ということは
２．探している数字は「7」より大きいよ
になりますね。
探している数字が「7」より大きいと分かった時点で「6」「7」は消せます。
「7」以下の数字は、探している数字ではないからです。
さぁ、いよいよラストスパートです。
残った数字の中から、さっきと同じように真ん中の数字を取り出します。
……って、残っている数字は「8」と「9」の2つしかありませんね。
とりあえず今回は「8」ということにしておきましょうか。
次に、さっきと同じように、探している数字が真ん中の数字よりも大きいか小さいかを確認します。
１．探している数字は「8」だよ
２．探している数字は「8」より大きいよ
３．探している数字は「8」より小さいよ
のどれかを確認するわけです。
今回、探しているのは「8」です。
ということは
１．探している数字は「8」だよ
になりますね。
これで探していたデータが見つかりました。
このような「半分ずつ消去法」なデータの探し方が二分探索です。
１．真ん中のデータを基準にして、条件に合わない方を消す
２．１を繰り返して最後まで残ったのが探しているデータ
な やり方です。
二分探索のメリットは
１．データの量が増えても、そんなに探す時間が変わらない
２．探しているデータがどれでも、見つかるまでの時間が同じくらい
でしょうか。
二分探索では1回の絞り込みで候補が半分になります。
ということは、データが倍になっても絞り込みの回数は1回しか増えないわけです。
例えば、10個の数字から1個の数字を探す場合、絞り込み回数は最大3回です。
倍の20個の数字の中から探すことになっても絞り込み回数は最大4回で済みます。
1回絞り込んだ時点で候補は（20個の半分の）10個になるからです。
これが「１．データの量が増えても、そんなに探す時間が変わらない」です。
また、二分探索では、探すデータがどれでも見つかるまでの時間が同じくらいです。
例えば、10個の数字から1個の数字を探す場合、絞り込み回数は最大で3回です。
「1」を探すのでも「8」を探すのでも（ピンポイントで真ん中の値に該当しない限り）絞り込み回数は3回になります。
探す値によって1回で済んだり100回もかかったりといったバラツキがありません。
探すのにかかる時間を、ある程度は標準化できるのです。
これが「２．探しているデータがどれでも、見つかるまでの時間が同じくらい」です。
一方のデメリットは
データが順番に並んでいないと使えない
でしょうか。
バラバラのデータに対して二分探索を使いたい場合は、順番を並べ直す必要があります。
順番を並べ直すのが大変な場合は、二分探索を使わない方が良かったりするわけです。
一言でまとめるよ
まぁ「二分探索」って単語が出てきたら「順番に並んだデータを真ん中で半分に分けて候補を絞っていく やり方なんだな～」と お考えください。
