0.背景

二分探索を初めて学習してから数年、今更二分探索を学習する機会があり、

「分割する個数を増やしても計算時間は二分探索より早くならないのか？」

という単純な疑問が浮かんだ。
サイズNの配列をx(>2)個の領域に分割すれば、計算時間はlogx　N * １ループ当たりの比較回数となり、logx N < log2 Nなので、１ループ当たりの比較回数次第では早くならないか？と思ったからである。

しかしWebで検索してみたが、探索アルゴリズムの一環としてのX分探索に関する記事は(少なくとも日本語では)見つからなかった。

また「凸関数の極値を求める」という目的における三分探索や黄金比探索といった探索アルゴリズムがあることを知ったが、今回は二分探索と同様の目的における探索アルゴリズムを対象にするため、本稿では対象外とした。

参考
・ 実数探索三種類解説 -nodchipの日記
・ 三分探索と黄金分割探索 -naoya_t@hatenablog

よって本稿では、上記の疑問を解決するために、数学的に二分探索がX分探索において理論上最速であることを示した経緯を記す。
また、二分探索についての解説は様々な所で行われているので本稿では割愛する。

1.前提条件

今回は、
「ソート済みの配列に対し、与えられた値が配列のどこに存在するかを検索すること」
を目的とする探索アルゴリズムについて考える。

また二分探索からくる造語であるX分探索は、
「配列をX個に分割し、それぞれの境界値と探索する値の大小を比較し、探索する値が当てはまる領域を次の配列として繰り返し探索するアルゴリズム」
として考えて頂きたい。

2.三分探索

まずX分探索の理解のため、三分探索から考える。

三分探索のアルゴリズムも基本的には二分探索と同じように、

1.kとb1を比較
　　
　　1-1.k<b1の時、αを次の探索範囲にして繰り返し

　　1-2.k=b1の時、終了

　　1-3.k>b1の時、次へ

2. kとb2を比較

　　2-1.k<b2の時、βを次の探索範囲にして繰り返し

　　2-2.k=b2の時、終了

　　2-3.k>b2の時、γを次の探索範囲にして繰り返し    

とした。
その時の比較回数は図に示すように、

• kが領域α内の時はkとb1の比較だけなので1回
• それ以外の時はkとb1・b2の比較なので２回

となる。

よって、比較回数の期待値は (1+2+2)/3 = 5/3 となり、三分探索の計算時間は、

と考えられる。
二分探索と比較すると、

より、三分探索は二分探索に比べ理論上約1.05倍の計算時間になることが分かった。

3.X分探索

一般化してX分探索を考える。

三分探索と同様に考えて、比較回数の期待値は、

よって、X分探索の計算時間は、

となり、二分探索と比較すると、

ここで、

を示せばX分探索が二分探索より計算時間がかかることが証明できる。
ここからの証明が上手く出来ず、泥臭くなってしまった。。。

ここで、x≧4において、

なので、

がx≧4において成立することを示したい。
f(x)=(左辺)として、微分して極値を求めるとx=2/log2(≒2.8)になり、x≧4でf(x)は単調増加になるので、

以上より、X分探索は二分探索より計算時間がかかることが証明された。

終わりに

ここまで書いて、恐らく大多数の人にとって役立たない記事だと思っています、が、もし僕と同じ疑問を持った方が居て見て頂けたら幸いです。
そもそも感覚的にこんな疑問持たなくない？という方がいましたら、僕の中で何か考えが抜けてる気がするので、コメントでご指摘頂けたら嬉しいです。

長文・駄文お付き合い下さりありがとうございました。