sub binary_search {
#Called like this:
#binary_search(\@data, $#data, $num);
my ($aref, $high_index, $target) = @_;
my $low_index = 0;
if ( $target < $aref->[$low_index]
or $target > $aref->[$high_index] ) {
die "Target not in range."
}
my ($middle_index, $middle_value);
while ($low_index <= $high_index) {
$middle_index = int( ($high_index + $low_index)/2 );
$middle_value = $aref->[$middle_index];
print '.'; #print a dot for each attempt to locate target
if ($middle_value < $target) {
$low_index = $middle_index + 1;
}
elsif ($middle_value > $target) {
$high_index = $middle_index - 1;
}
elsif ($middle_value == $target) {
print "*"; #Indicates the target is actually in @data
return $middle_index == 0
? ($middle_value, $aref->[1])
: ($aref->[$middle_index-1], $middle_value)
;
}
}
while ($aref->[$low_index] >= $target) {
--$low_index;
}
return $aref->[$low_index], $aref->[$low_index+1];
}
say '';
my @data = (1, 5, 6, 7, 8, 9, 10, 20, 30, 33, 34, 38, 41, 100, 101, 102, 110);
for my $num (1 .. $data[-1]) {
my @results = binary_search(\@data, $#data, $num);
say "$num: @results";
}
--output:--
....*1: 1 5
....2: 1 5
....3: 1 5
....4: 1 5
...*5: 1 5
....*6: 5 6
..*7: 6 7
....*8: 7 8
...*9: 8 9
....*10: 9 10
.....11: 10 20
.....12: 10 20
.....13: 10 20
.....14: 10 20
.....15: 10 20
.....16: 10 20
.....17: 10 20
.....18: 10 20
.....19: 10 20
.....*20: 10 20
.....21: 20 30
.....22: 20 30
.....23: 20 30
.....24: 20 30
.....25: 20 30
.....26: 20 30
.....27: 20 30
.....28: 20 30
.....29: 20 30
.*30: 20 30
....31: 30 33
....32: 30 33
....*33: 30 33
...*34: 33 34
....35: 34 38
....36: 34 38
....37: 34 38
....*38: 34 38
....39: 38 41
....40: 38 41
..*41: 38 41
....42: 41 100
....43: 41 100
....44: 41 100
....45: 41 100
....46: 41 100
....47: 41 100
....48: 41 100
....49: 41 100
....50: 41 100
....51: 41 100
....52: 41 100
....53: 41 100
....54: 41 100
....55: 41 100
....56: 41 100
....57: 41 100
....58: 41 100
....59: 41 100
....60: 41 100
....61: 41 100
....62: 41 100
....63: 41 100
....64: 41 100
....65: 41 100
....66: 41 100
....67: 41 100
....68: 41 100
....69: 41 100
....70: 41 100
....71: 41 100
....72: 41 100
....73: 41 100
....74: 41 100
....75: 41 100
....76: 41 100
....77: 41 100
....78: 41 100
....79: 41 100
....80: 41 100
....81: 41 100
....82: 41 100
....83: 41 100
....84: 41 100
....85: 41 100
....86: 41 100
....87: 41 100
....88: 41 100
....89: 41 100
....90: 41 100
....91: 41 100
....92: 41 100
....93: 41 100
....94: 41 100
....95: 41 100
....96: 41 100
....97: 41 100
....98: 41 100
....99: 41 100
....*100: 41 100
...*101: 100 101
....*102: 101 102
.....103: 102 110
.....104: 102 110
.....105: 102 110
.....106: 102 110
.....107: 102 110
.....108: 102 110
.....109: 102 110
.....*110: 102 110
####
use List::BinarySearch qw(bsearch_num_pos);
...
...
sub cpan_binary_search {
my ($aref, $high_index, $target) = @_;
my $low_index = 0;
if ( $target < $aref->[$low_index]
or $target > $aref->[$high_index] ) {
die "Target not in range."
}
my $index = bsearch_num_pos($target, @$aref);
return $index == 0 ? ($aref->[0], $aref->[1])
: ($aref->[$index-1], $aref->[$index]);
}
my @data = (1, 5, 6, 7, 8, 9, 10, 20, 30, 33, 34, 38, 41, 100, 101, 102, 110);
for my $num (1 .. $data[-1]) {
my @results = cpan_binary_search(\@data, $#data, $num);
say "$num: @results";
}
##
##
use strict;
use warnings;
use 5.012;
say for @ARGV;
say "\n";
my ($in, $out) = @ARGV;
say $in;
say $out;
--output:--
$ perl prog1.pl infile_name outfile_name 10 20
infile_name
outfile_name
10
20
infile_name
outfile_name