はてなブックマーク

0.背景 二分探索を初めて学習してから数年、今更二分探索を学習する機会があり、 「分割する個数を増やしても計算時間は二分探索より早くならないのか？」 という単純な疑問が浮かんだ。 サイズNの配列をx(>2)個の領域に分割すれば、計算時間はlogx　N * １ループ当たりの比較回数となり、logx N < log2 Nなので、１ループ当たりの比較回数次第では早くならないか？と思ったからである。 しかしWebで検索してみたが、探索アルゴリズムの一環としてのX分探索に関する記事は(少なくとも日本語では)見つからなかった。 また「凸関数の極値を求める」という目的における三分探索や黄金比探索といった探索アルゴリズムがあることを知ったが、今回は二分探索と同様の目的における探索アルゴリズムを対象にするため、本稿では対象外とした。 参考 ・ 実数探索三種類解説 -nodchipの日記 ・ 三分探索と黄金分