Yes you can do a binary search. Yet is will find the correct placement faster for large lists. In fact I have a module on cpan called File::SortedSeek that implements binary searches in large files so I appreciate the algorithm :-) However in this scenario having found the index you then have a practical problem. It is not possible to insert a value into the middle of an array, which is really just a contiguous sequence of SV* What you have to do is make space for it. Splice does that by moving a large chunk (or the entire array). The bubble algorithm also does it and is (in past testing) about twice as fast as just calling sort. Here is a binary search implementation. Benchmarking the options is left to you.
my @ary = (1..4, 6..10);
for my $val( 0, 5, 11, 0, 5, 11 ) {
binary( \@ary, $val );
print "@ary\n";
}
sub binary {
my ( $ary, $val ) = @_;
my ( $min, $max, $last, $i ) = ( 0, scalar @{$ary}, 0, 0 );
while ( 1 ) {
$i = int( ($min+$max)/2 );
# print "i=$i\n";
last if $last == $i;
$last = $i;
if ( $ary->[$i] < $val ) {
$min = $i;
}
elsif ( $ary->[$i] > $val ) {
$max = $i;
}
else {
# values are equal so we have a valid index
last;
}
}
$i++ if $i; # for index 0 we want that, otherwise we want next p
+osition
splice @$ary, $i, 0, $val;
}
__DATA__
0 1 2 3 4 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10 11
0 0 1 2 3 4 5 6 7 8 9 10 11
0 0 1 2 3 4 5 5 6 7 8 9 10 11
0 0 1 2 3 4 5 5 6 7 8 9 10 11 11
|