GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  MATH::INTERVALSEARCH (3)

.ds Aq ’

NAME

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

CONTENTS

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

<B>interval_searchB> 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.

POD ERRORS

Hey! <B>The above document had some coding errors, which are explained below:B>
Around line 244: =back doesn’t take any parameters, but you said =back 4
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 MATH::INTERVALSEARCH (3) 2013-11-10

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.