Blair Zajac >
Math-Interpolate-1.05 >
Math::IntervalSearch

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

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);

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 <=.

**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.

Blair Zajac <bzajac@geostaff.com>.

Copyright (c) 1998 by Blair Zajac.

syntax highlighting: