駆け出し出遅れプログラミング初心者の日記

　こんにちはです。鳥居です。

今回は二分探索についてまとめていこうと考えています。

とはいえ流石に私なんかより皆さんのほうが二分探索について詳しいと思うので参考にはならないとは思うのですが、、、

　とりあえず二分探索の具体的な方法について書くと、

・あるソートされたリストから特定の条件を満たす値(ある数未満の中で最大の値など)を求めるとする

・適当にとても小さい値ととても大きな値(それぞれ-INFとINFとして定義されることが多いですね)をとる。

・それらの値を足して２で割った数(中央値)より大きければ中央値を小さいほうの値に再設定し、小さければ中央値を大きいほうの値に再設定することを繰り返す。

・最終的に小さいほうの値と大きいほうの値の差がなくなった時求めたい値が出てくる

こんな感じですかね。…相変わらず説明が下手だorz。

さて、この二分探索ですが、普通の探索と比べて何が良いのでしょうか？

まず、「走査したいリストの要素数が比較的大きくても計算量が少なくて済む」ところですね。

例えば要素数が10^18ほどあるリストだと、普通の探索では最悪それに比例した時間(10^18)がかかってしまいますが、これが二分探索だとlogがつくおかげでlog10^18=18*log10≒54と、圧倒的に計算量が小さくなります。これは驚きですね。

また、「あるN個の要素からなるリストから二個値を取り出して特定の値を求めたい」時なども、通常はN個要素それぞれに対してN－１個の要素を試していくとおおよそN^2の計算量がかかることになってしまいますが、片方の要素を全て試し、もう片方の要素を二分探索するといった方法を用いればNlogNの計算量となり、これも大幅な時間短縮となります。

このように、アルゴリズムを工夫するだけで計算にかかる時間が驚くほど速くなるというのは非常に魅力的です。是非自分でも取り入れていきたいですね。