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

質問

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

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

回答No.3

ballville · ベストアンサー

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

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

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

１）辞書を真ん中で開く。
２）そのページの項目語と「ニブンタンサク」を辞書順で比較（後ろが大）する。
項目語＝「ニブンタンサク」　－＞発見　ループ終了
項目語＞「ニブンタンサク」　－＞そのページより前の部分を全体の辞書だとみなして１へ
項目語＜「ニブンタンサク」　－＞そのページより後ろを全体の辞書だとみなして１へ

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

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

参考URL：

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

回答No.4

superside0

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

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

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

回答No.2

neKo_quatre

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

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

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

回答No.1

山田 太郎（@f_a_007）

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

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