File Coverage

blib/lib/Search/Binary.pm
Criterion Covered Total %
statement 34 36 94.4
branch 9 10 90.0
condition 3 5 60.0
subroutine 5 5 100.0
pod 0 1 0.0
total 51 57 89.4


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__