Search::Binary - generic binary search

Search-Binary documentation Contained in the Search-Binary distribution.

Index

Code Index:

NAME

Top

Search::Binary -- generic binary search

SYNOPSIS

Top

  use Seach::Binary;
  $pos = binary_search($min, $max, $val, $read, $handle, [$size]);

DESCRIPTION

Top

binary_search implements a generic binary search algorithm returning the position of the first record whose index value is greater than or equal to $val. The search routine does not define any of the terms position, record or index value, but leaves their interpretation and implementation to the user supplied function &$read(). The only restriction is that positions must be integer scalars.

During the search the read function will be called with three arguments: the input parameters $handle and $val, and a position. If the position is not undef, the read function should read the first whole record starting at or after the position; otherwise, the read function should read the record immediately following the last record it read. The search algorithm will guarantee that the first call to the read function will not be with a position of undef. The read function needs to return a two element array consisting of the result of comparing $val with the index value of the read record and the position of the read record. The comparison value must be positive if $val is strictly greater than the index value of the read record, 0 if equal, and negative if strictly less. Furthermore, the returned position value must be greater than or equal to the position the read function was called with.

The input parameters $min and $max are positions and represents the extent of the search. Only records which begin at positions within this range (inclusive) will be searched. Moreover, $min must be the starting position of a record. If present $size is a difference between positions and determines when the algorithms switches to a sequential search. $val is an index value. The value of $handle is of no consequence to the binary search algorithm; it is merely passed as a convenience to the read function.

COPYRIGHT

Top

  Copyright 1998, Erik Rantapaa

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

Search-Binary documentation Contained in the Search-Binary distribution. 
#
# $Id: Binary.pm,v 1.5 1998/12/15 20:55:08 rantapaa Exp $
#
# Seach::Binary

package Search::Binary;


# use strict;
require Exporter;
@ISA = qw(Exporter);
@EXPORT = qw(binary_search);

$VERSION = "0.95";

sub binary_search {
	my $posmin = shift;
	my $posmax = shift;
	my $target = shift;
	my $readfn = shift;
	my $handle = shift;
	my $smallblock = shift || 512;

	my ($x, $compare, $mid, $lastmid);
	my ($seeks, $reads);

	# assert $posmin <= $posmax

	$seeks = $reads = 0;
	$lastmid = int(($posmin + $posmax)/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)/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;
	}
	wantarray ? ($posmin, $seeks, $reads) : $posmin;
}

1;