2分探索木

2分探索木とは

配列が整列されている事を利用し、探索する数を半分ずつ減らす事で効率良く数を探索することが出来る。

[例1] 1 2 3 4 ⑤ 6 7 8 9 　　　※6を探したいとする

この場合の配列の基準値は５になる。
5<6であることから6は5より右側にあることがわかる。左側にある全ての値は削除。

[After] ６ ⑦ 8 9

この場合の配列の基準値は7となる。
6<7なので6は7の左側にあることがわかる。右側にある全ての値は削除。

この他の例題もこなした感じだと、このように偶数になった場合に配列２つに分割して、
その手前側の一番最後の値を配列の中心値として定義しているようだ。
この点は調べていないので要チェック

[last] ⑥

6=6となり探索が完了した。

■アルゴリズム図鑑
http://algorithm.wiki/ja/app/