[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

二分探索

pointこの用語のポイント

point検索のやり方だよ

point半分に分けて条件に合わない方を消すよ

point複数回繰り返すことで、最終的に探したいもの1つが見つかるよ

スポンサーリンク

簡単に書くよ

二分探索とは

「半分ずつ消去法」な検索のやり方のこと
です。

image piyo

詳しく書くよ

データが順番に並んでいることが前提条件な検索のやり方です(--)b

「真ん中の値を取って『それより大きい?小さい?』と質問を繰り返す」ことでデータを探していきます。

例えば「1,2,3,4,5,6,7,8,9」の数字があってその中から「8」を探すとしましょう。

まずは真ん中の値を取ります。

「5」ですね。

まず最初に「探している数字は『5』ですか~?『5』より大きいですか~?それとも小さいですか~?」と訊きます。

今回探しているのは「8」なので「『5』より大きいで~す」とお返事が返ってきます。

お返事が「『5』で~す」であれば、探している数字は「5」と分かります。
お返事が「『5』より大きいで~す」であれば、探している数字は「6,7,8,9」のどれかだと分かります。
お返事が「『5』より小さいで~す」であれば、探している数字は「1,2,3,4」のどれかだと分かります。

今回のお返事は「『5』より大きいで~す」なので探している数字は「6,7,8,9」のどれかだと分かりました。

次はこの「6,7,8,9」に対してさっきと同じように真ん中の値を取ります。

「7」か「8」ですね。
取りあえず今回は「7」ってことにしておきましょうか。

それではまた「探している数字は『7』ですか~?『7』より大きいですか~?それとも小さいですか~?」と訊きます。

今回探しているのは「8」なので「『7』より大きいで~す」とお返事が返ってきます。

お返事が「『7』で~す」であれば、探している数字は「7」と分かります。
お返事が「『7』より大きいで~す」であれば、探している数字は「8,9」のどちらかだと分かります。
お返事が「『7』より小さいで~す」であれば、探している数字は「6」だと分かります。

今回のお返事は「『7』より大きいで~す」なので探している数字は「8,9」のどれかだと分かりました。

よっしゃ!ラストスパート!

次はこの「8,9」に対してさっきと同じように真ん中の値を取ります。

「8」か「9」ですね。

って、二択じゃん(--)ノノ^_

取りあえず今回は「8」ってことにしておきましょうか。

それではまた「探している数字は『8』ですか~?『8』より大きいですか~?それとも小さいですか~?」と訊きます。

今回探しているのは「8」なので「『8』で~す」とお返事が返ってきます。

これで検索は完了です\(--)/
この方式で調べていくと、10個の数字から1つを探すのに3回の質問で済みました。

このように「1回の質問で候補を半分に絞っていく検索のやり方」が「二分探索」です。

ここまでの説明が長ったらしいのでややこしく感じるかもしれませんが、理屈は単純ですよ。
「真ん中の値を取ってそれと一致するか。一致しないなら大きいか小さいか」を訊いていくだけです。

一回質問をするごとに候補が半分に減っていきますよね?
だから候補が倍になっても質問の回数が一回増えるだけです。
候補の数が多くなっても質問の回数はそんなに増えないわけです。
つまり

探すのに掛かる時間が候補の数が増えてもあまり変わらない。

それがこの方法のメリットその1(--)b

もう1つメリットがあります。
それは

探したい値がどれでも見つかるまでに掛かる時間がほぼ同じこと。

10個の数字から1個の数字を探す場合、質問回数は3回です。
もちろん途中で見つかっちゃう可能性はありますが、どんなに多くても3回です。

つまり10個の数字から1個の数字を探す場合に掛かる時間は質問3回分と予想ができますね。
探す値によって質問が1回で済んだり100回も掛かったりしません。
そのため検索に掛かる時間をある程度標準化することができるのです。

image piyo2

一言でまとめるよ

まぁ「二分探索」って単語が出てきたら「半分に分けて候補を絞っていく検索のやり方なんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク