こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

二分探索は木のように例えられる?

二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか?

回答のほうよろしくお願いいたします。

投稿日時 - 2019-03-19 23:01:53

QNo.9598528

すぐに回答ほしいです

質問者が選んだベストアンサー

 「木の枝」は前の方が書かれているように、データ全体の論理構造を図示した時の形からくるものです。

 検索アルゴリズムを「分かりやすい例え」で理解するなら、辞書を引くことだと考えるといいでしょう。二分探索はデータが整列していることが前提なので、文字通り「辞書順」で項目が並んでいる辞書はうってつけです。

 「コンピュータ用語辞典」(そんな辞書があるかどうか知りませんが)で「二分探索(ニブンタンサク)」を調べるときのことを考えます。実際の辞書は1ページに複数の項目があったりしますが、話を簡単にするため見開き2ページで1項目が載っているとします。

1)辞書を真ん中で開く。
2)そのページの項目語と「ニブンタンサク」を辞書順で比較(後ろが大)する。
項目語=「ニブンタンサク」 ->発見 ループ終了
項目語>「ニブンタンサク」 ->そのページより前の部分を全体の辞書だとみなして1へ
項目語<「ニブンタンサク」 ->そのページより後ろを全体の辞書だとみなして1へ

※今、辞書に載っていなかったときのことは考えていません。

このような手順でループを回すと、
毎回データを二つに分けている=探すべきデータが半分に減る
ことで高速に検索できることがわかります。

参考URL:https://codezine.jp/article/detail/9900?p=2

投稿日時 - 2019-03-20 15:39:16

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.4

二分探索(バイナリサーチ)は ソート済の配列から特定の値の場所を取り出す手法
(半分にして対象外の値を除去しながら探索するので総当りしなくてすむ)

二分探索木(バイナリサーチツリー)は、各ノードから別のノードへの枝が2本生えている木構造のリスト構造体からノード位置を取り出す手法
(値の大小でノードの方向が決まるので 総当りしなくてすむ)

で別ものですが、これを混同してないでしょか。

投稿日時 - 2019-03-22 10:40:55

ANo.2

図を描くと木のように見える事があるってだけでは。

> 木の枝が伸びるような感じで探索する感じでしょうか?

生物の成長をシミュレーションとかしたものではないし。
木の枝が必ず全部の探索空間を網羅するものでもないし。

投稿日時 - 2019-03-20 08:55:49

ANo.1

Q、二分探索とは、木の枝が伸びるような感じで探索する感じでしょうか?
A、否。

二分木探索は、木の枝に例えられてもバイナリーサーチのイメージと木は結びつかない。

投稿日時 - 2019-03-20 08:40:39

あなたにオススメの質問