NAME

Math::IntervalSearch - Search where an element lies in a list of sorted elements

SYNOPSIS

 use Math::IntervalSearch qw(interval_search);
 my @array = (1..5);
 my $location = interval_search(2.4, \@array);

 # Use your own comparison operators.
 sub ReverseLessThan {
   $_[0] < $_[1];
 }

 sub ReverseLessThanEqualTo {
   $_[0] <= $_[1];
 }

 $location = interval_search(2.4,
                             \@array,
                             \&ReverseLessThan,
                             \&ReverseLessThanEqualTo);

DESCRIPTION

This subroutine is used to locate a position in an array of values where a given value would fit. It has been designed to be efficient in the common situation that it is called repeatedly. The user can supply a different set of comparison operators to replace the standard < and <=.

SUBROUTINES

interval_search value sequence [less_than [less_than_equal_to]]

Given a value interval_search returns the location in the reference to an array sequence where the value would fit. The default < operator to compare the elements in sequence can be replaced by the subroutine less_than which should return 1 if the first element passed to less_than is less than the second. The default <= operator to compare the elements in sequence can be replaced by the subroutine less_than which should return 1 if the first element passed to less_than is less than the second.

The values in sequence should already be sorted in numerically increasing order or in the order that would be produced by using the less_than subroutine.

Let N be the number of elements in referenced array sequence, then interval_search returns these values: -1 if value < sequence->[0] i if sequence->[i] <= value < sequence->[i+1] N-1 if sequence->[N-1] <= value

If a reference is made to an empty array, then -1 is always returned.

If there is illegal input to interval_search, such as an improper number of arguments, then an empty list in list context, an undefined value in scalar context, or nothing in a void context is returned.

This subroutine is designed to be efficient in the common situation that it is called repeatedly, with value taken from an increasing or decreasing list of values. This will happen, e.g., when an irregular waveform is interpolated to create a sequence with constant separation. The first guess for the output is therefore taken to be the value returned at the previous call and stored in the variable ilo. A first check ascertains that ilo is less than the number of data points in sequence. This is necessary since the present call may have nothing to do with the previous call. Then, if sequence->[ilo] <= value < sequence->[ilo+1],

we set left = ilo and are done after just three comparisons. Otherwise, we repeatedly double the difference istep = ihi - ilo

while also moving ilo and ihi in the direction of x, until sequence->[ilo] <= x < sequence->[ihi],

after which bisection is used to get, in addition, ilo+1 = ihi.

Then left = ilo is returned.

AUTHOR

Blair Zajac <blair@orcaware.com>.

COPYRIGHT

Copyright (C) 1998-2005 Blair Zajac. All rights reserved. This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.