File Coverage

blib/lib/Search/Binary.pm

Criterion	Covered	Total	%
statement	37	39	94.8
branch	10	12	83.3
condition	3	5	60.0
subroutine	5	5	100.0
pod	0	1	0.0
total	55	62	88.7

package Search::Binary;

use strict;
use warnings;
use Carp;
use parent 'Exporter';
our @EXPORT = qw(binary_search);

our $VERSION = '0.96_02';

sub binary_search {
    my ($posmin, $posmax, $target, $readfn, $handle, $smallblock) = @_;
    $smallblock ||= 0;
    if ($posmin > $posmax) {
        carp 'First argument must be less then or equal to second argument'
            . " (min: $posmin, max: $posmax)";
        return 0; # some libraries rely on this behavior
    }

    my ($x, $compare, $mid);

    # assert $posmin <= $posmax

    my $seeks = my $reads = 0;
    my $lastmid = int($posmin + (($posmax - $posmin) / 2)) - 1;
    while ($posmax - $posmin > $smallblock) {

        # assert: $posmin is the beginning of a record
        # and $target >= index value for that record

        $seeks++;
        $x = int($posmin + (($posmax - $posmin) / 2));
        ($compare, $mid) = $readfn->($handle, $target, $x);

        unless (defined($compare)) {
            $posmax = $mid;
            next;
        }
        last if ($mid == $lastmid);
        if ($compare > 0) {
            $posmin = $mid;
        } else {
            $posmax = $mid;
        }
        $lastmid = $mid;
    }

    # Switch to sequential search.

    $x = $posmin;
    while ($posmin <= $posmax) {

        # same loop invarient as above applies here

        $reads++;
        ($compare, $posmin) = $readfn->($handle, $target, $x);
        last unless (defined($compare) && $compare > 0);
        $x = undef;
    }
    return wantarray ? ($posmin, $seeks, $reads) : $posmin;
}

1;
__END__