【基本情報】初心者向け！2分探索を完全に理解する！

お茶ん太

この記事では、2分探索について、初心者にも分かりやすく、図解付きで丁寧に解説しています！

2分探索

2分探索は以下の方法でデータを探す方法。
①データを昇順(小さいもの順)に並べる。
②真ん中にある数字を見る。
③②で見た数字と探したい数字を比較する。
④探したい数字の方が小さい場合は前半の数字で②と③を行い、大きい場合は後半の数字で②と③を行う。
⑤探したい数字が見つかるまで②～④を繰り返す。
2分探索木は2分探索が出来るデータの構造や探し方を分かりやすく図で表したもの。

2分探索
2分探索木
- 2分探索木を色々な視点で見てみる
  - 節の値を一番下に降ろして見ると
  - 箱を開ける順番
基本情報技術者試験での出題例

2分探索

突然ですが、次の問題をどうやって解きますか？「①～⑩の箱の中に1~100までの数字がランダムに入っています。ただし、①～⑩の順番で入ってる数字は大きくなります。では、25はどの箱に入っているでしょうか。」

適当に開けていきますか？①から順番に開けていきますか？実は効率良く探す方法があります。それが2分探索です。2分探索では次の手順で値の探索をします。

真ん中の値を調べる。
真ん中の値と探したい値を比較する。探したい値の方が大きい場合、真ん中より後ろに探したい値があることが分かる。探したい値の方が小さい場合、真ん中より前側に探したい値があることが分かる。ここで、探したい値が真ん中より前半にあるか後半にあるか分かる。
②で探したい値が真ん中より前半か後半か分かったので、更にその範囲の真ん中の値を調べる。
②でやったのと同じように、その範囲の中で探したい値が真ん中より前半にあるか後半にあるか調べる。
③でやったのと同じように、更に絞った範囲の真ん中の値を調べる。
これを繰り返すことで探したい値がどこにあるか調べる。

具体的に見てみましょう。まず真ん中の箱(⑤)を開けます。⑤には68が入っていたので、25は前半(①～④)にあることが分かります。

ということで次は①～④の真ん中の箱、③の箱を開けます(②でもOKです)。③には19が入っていたので、①～④の後半(④)にあることが分かります。

ということで④の箱を開けてみましょう。④には25が入っていました。

2分探索では効率良く値を探せると言いました。どれくらい効率良いかと言うと、箱が10000個あったとしても平均13回で探せるくらいです。

2分探索では効率良く値を探せるので、最初から2分探索しやすいようにデータを格納したいですよね。では、どのようにデータを格納すれば2分探索しやすくなるのか？そのデータ構造を分かりやすく図にしたものが2分探索木になります。

2分探索木

2分探索木とは、2分探索できるデータの格納方法や2分探索ってどうやるの？という方法を分かりやすく図にしたものです。

先程の箱を全て開けてみましょう。

これらの数字を2分探索木に表すと下図のようになります。〇の部分を節(ノード)と言い、節と節を繋いだ線を枝(ブランチ)を言います。

2分探索木には上の節より大きい数字は右側の節に、小さい数字は左側の節に格納するというルールがあります。

2分探索木を色々な視点で見てみる

節の値を一番下に降ろして見ると

節の値を一番下に降ろしてみましょう。すると、一番左が小さく、右に行くにつれて大きくなっていることが分かります。2分探索は値が昇順になっていなければ出来ません。その特徴を表していることが分かりますね。

箱を開ける順番

2分探索木では2分探索でどの箱を開けるべきか分かります。68は全ての値の中央にある値なので、1回目に開ける箱になります。また、19と83はそれぞれ【3,11,19,25】の中央にある値、【69,80,83,92,98】の中央にある値なので、2回目に開ける箱になります。
このように、2分探索木で上にある節の箱から開けていけば2分探索になると分かります。