内部探索(interpolation search)

データが均等なランダムの場合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 ( $i ) {
    print "============find===============\n";
    print "index: $i\n";
    print "value: $a[$i]\n";
    print "===============================\n";
} else {
    print "============not find===============\n";
}



# interpolation search
# 内挿探索

sub find {
    my ($a, $v) = @_;

    my $l = 0;
    my $r = $#$a;

    while ( $a[$l] <= $v && $a[$r] >= $v ) {
        my $mid = int($l + ($v - $a[$l]) *  ($r - $l) / ( $a->[$r] - $a->[$l] ));

        if ( $a[$mid] > $v ) {
            $r = $mid - 1;
        }elsif ( $a[$mid] < $v ) {
            $l = $mid + 1;
        }else{
            return $mid;
        }
        print $l. ":". $r. "\n";
    }

    return undef;
}