Wow, 36500% faster. That's a worthwhile saving. Glad it helped. It's always good to use a geometric search rather than a linear one when you have any form of sorted data that you can use the split the dif algoritm on. The number of tries to find the desired position is given by:

print "Num items  Geom avg  Lin avg  Lin:Geom\n";
for ( my $num_items = 2; $num_items < 2<<20; $num_items <<= 1 ) {
    # geometric
    my $geom_max = int(log($num_items)/log(2))+1;
    my $geom_avg = int(log(($num_items/2))/log(2))+1;
    
    # linear
    my $lin_max = $num_items;
    my $lin_avg = $num_items/2;
    
    printf "%8d %8d %8d %8d\n", 
    $num_items, $geom_avg, $lin_avg, $lin_avg/$geom_avg;
}
[download]

Should wrap it in a module one day :-)

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print