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 <blair@orcaware.com>.
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.
Hey!
The above document had some coding errors, which are explained
below:
- Around line 244:
- =back doesn't take any parameters, but you said =back 4