totofuga https://blog.hatena.ne.jp/totofuga/ totofugaのブログ https://totofuga.hateblo.jp/ perl アルゴリズム データが均等なランダムの場合loglogNの速度になるため、 binary searchより効率がよくなるが、 一つの計算時間は増えるため、データがかなり大きい場合にのみ有効。 やってることは、binary searchのメディアンの選び方を現在のデータから 有効そうな位置を取得してるだけ。 http://en.wikipedia.org/wiki/Interpolation_search perlの実装 my @a = map { int (rand() * 100) } 0..99; @a = sort { $a <=> $b } @a; my $i = find(\@a, 50); if… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftotofuga.hateblo.jp%2Fentry%2F2015%2F01%2F13%2F132419" title="内部探索(interpolation search) - totofugaのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-01-13 13:24:19 rich https://totofuga.hateblo.jp/entry/2015/01/13/132419 1.0 100%