interv Subroutine

The XT array is a set of increasing values.  The goal of the routine
is to determine the largest index I so that XT(I) <= X.

The routine is designed to be efficient in the common situation
that it is called repeatedly, with X taken from an increasing
or decreasing sequence.

This will happen when a piecewise polynomial is to be graphed.
The first guess for LEFT is therefore taken to be the value
returned at the previous call and stored in the local variable ILO.

A first check ascertains that ILO < LXT.  This is necessary
since the present call may have nothing to do with the previous
call.  Then, if

  XT(ILO) <= X < XT(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

  XT(ILO) <= X < XT(IHI)

after which we use bisection to get, in addition, ILO + 1 = IHI.
The value LEFT = ILO is then returned.

14 February 2007

Carl DeBoor

Carl DeBoor,
A Practical Guide to Splines,
Springer, 2001,
ISBN: 0387953663,
LC: QA1.A647.v27.

Input, real ( kind = 8 ) XT(LXT), a nondecreasing sequence of values.

Input, integer ( kind = 4 ) LXT, the dimension of XT.

Input, real ( kind = 8 ) X, the point whose location with 
respect to the sequence XT is to be determined.

Output, integer ( kind = 4 ) LEFT, the index of the bracketing value:
  1     if             X  <  XT(1)
  I     if   XT(I)  <= X  < XT(I+1)
  LXT   if  XT(LXT) <= X

Output, integer ( kind = 4 ) MFLAG, indicates whether X lies within the
range of the data.
-1:            X  <  XT(1)
 0: XT(I)   <= X  < XT(I+1)
+1: XT(LXT) <= X