/
ch-1.pl
67 lines (52 loc) · 1.35 KB
/
ch-1.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#!/usr/bin/perl
use strict;
use warnings;
use Math::Utils qw(floor);
my $search = $ARGV[0];
die "ERROR: Missing search key.\n" unless defined $search;
my @matrix = ( [ 1, 2, 3, 5, 7 ],
[ 9, 11, 15, 19, 20 ],
[ 23, 24, 25, 29, 31 ],
[ 32, 33, 39, 40, 42 ],
[ 45, 47, 48, 49, 50 ], );
my $found = 0;
foreach my $row (@matrix) {
($row->[0] > $search) and last;
$found = binary_search($row, $search);
$found and last;
}
print sprintf("%d %s.\n", $search, ($found)?("found"):("not found"));
=head1
Binary search algorithm as suggested by Wikipedia:
https://en.wikipedia.org/wiki/Binary_search_algorithm
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
=cut
sub binary_search {
my ($row, $target) = @_;
my $l = 0;
my $r = @$row - 1;
while ($l <= $r) {
my $m = floor(( $l + $r ) / 2);
if ($row->[$m] < $target) {
$l = $m + 1;
}
elsif ($row->[$m] > $target) {
$r = $m - 1;
}
else {
return $m;
}
}
return 0;
}