line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Search::Binary; |
2
|
|
|
|
|
|
|
|
3
|
4
|
|
|
4
|
|
61790
|
use strict; |
|
4
|
|
|
|
|
9
|
|
|
4
|
|
|
|
|
149
|
|
4
|
4
|
|
|
4
|
|
18
|
use warnings; |
|
4
|
|
|
|
|
6
|
|
|
4
|
|
|
|
|
106
|
|
5
|
4
|
|
|
4
|
|
21
|
use Carp; |
|
4
|
|
|
|
|
5
|
|
|
4
|
|
|
|
|
339
|
|
6
|
4
|
|
|
4
|
|
1334
|
use parent 'Exporter'; |
|
4
|
|
|
|
|
795
|
|
|
4
|
|
|
|
|
18
|
|
7
|
|
|
|
|
|
|
our @EXPORT = qw(binary_search); |
8
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
our $VERSION = '0.99'; |
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
sub binary_search { |
12
|
26
|
|
|
26
|
0
|
14747
|
my ($posmin, $posmax, $target, $readfn, $handle, $smallblock) = @_; |
13
|
26
|
|
50
|
|
|
109
|
$smallblock ||= 0; |
14
|
26
|
100
|
|
|
|
52
|
if ($posmin > $posmax) { |
15
|
1
|
|
|
|
|
190
|
carp 'First argument must be less then or equal to second argument' |
16
|
|
|
|
|
|
|
. " (min: $posmin, max: $posmax)"; |
17
|
1
|
|
|
|
|
32
|
return 0; # some libraries rely on this behavior |
18
|
|
|
|
|
|
|
} |
19
|
|
|
|
|
|
|
|
20
|
25
|
|
|
|
|
22
|
my ($x, $compare, $mid); |
21
|
|
|
|
|
|
|
|
22
|
|
|
|
|
|
|
# assert $posmin <= $posmax |
23
|
|
|
|
|
|
|
|
24
|
25
|
|
|
|
|
69
|
my $lastmid = int($posmin + (($posmax - $posmin) / 2)) - 1; |
25
|
25
|
|
|
|
|
61
|
while ($posmax - $posmin > $smallblock) { |
26
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
# assert: $posmin is the beginning of a record |
28
|
|
|
|
|
|
|
# and $target >= index value for that record |
29
|
|
|
|
|
|
|
|
30
|
103
|
|
|
|
|
122
|
$x = int($posmin + (($posmax - $posmin) / 2)); |
31
|
103
|
|
|
|
|
167
|
($compare, $mid) = $readfn->($handle, $target, $x); |
32
|
|
|
|
|
|
|
|
33
|
103
|
50
|
|
|
|
671
|
unless (defined($compare)) { |
34
|
0
|
|
|
|
|
0
|
$posmax = $mid; |
35
|
0
|
|
|
|
|
0
|
next; |
36
|
|
|
|
|
|
|
} |
37
|
103
|
100
|
|
|
|
184
|
last if ($mid == $lastmid); |
38
|
82
|
100
|
|
|
|
116
|
if ($compare > 0) { |
39
|
41
|
|
|
|
|
41
|
$posmin = $mid; |
40
|
|
|
|
|
|
|
} else { |
41
|
41
|
|
|
|
|
40
|
$posmax = $mid; |
42
|
|
|
|
|
|
|
} |
43
|
82
|
|
|
|
|
136
|
$lastmid = $mid; |
44
|
|
|
|
|
|
|
} |
45
|
|
|
|
|
|
|
|
46
|
|
|
|
|
|
|
# Switch to sequential search. |
47
|
|
|
|
|
|
|
|
48
|
25
|
|
|
|
|
26
|
$x = $posmin; |
49
|
25
|
|
|
|
|
50
|
while ($posmin <= $posmax) { |
50
|
|
|
|
|
|
|
|
51
|
|
|
|
|
|
|
# same loop invarient as above applies here |
52
|
|
|
|
|
|
|
|
53
|
50
|
|
|
|
|
79
|
($compare, $posmin) = $readfn->($handle, $target, $x); |
54
|
50
|
100
|
66
|
|
|
426
|
last unless (defined($compare) && $compare > 0); |
55
|
27
|
|
|
|
|
49
|
$x = undef; |
56
|
|
|
|
|
|
|
} |
57
|
25
|
|
|
|
|
135
|
return $posmin; |
58
|
|
|
|
|
|
|
} |
59
|
|
|
|
|
|
|
|
60
|
|
|
|
|
|
|
1; |
61
|
|
|
|
|
|
|
__END__ |