Suppose that you have decided to use some particular interpolation scheme, such as fourth-order polynomial interpolation, to compute a function f(x) from a set of tabulated xi ’s and fi ’s. Then you will need a fast way of finding your place | How to Search an Ordered Table 117 How to Search an Ordered Table Suppose that you have decided to use some particular interpolation scheme such as fourth-order polynomial interpolation to compute a function f x from a set of tabulated xfs and fa s. Then you will need a fast way of finding your place in the table of x s given some particular value x at which the function evaluation is desired. This problem is not properly one of numerical analysis but it occurs so often in practice that it would be negligent of us to ignore it. Formally the problem is this Given an array of abscissas xx j j 1 2 . n with the elements either monotonically increasing or monotonically decreasing and given a number x find an integer j such that x lies between xx j and xx j 1 . For this task let us define fictitious array elements xx 0 and xx n 1 equal to plus or minus infinity in whichever order is consistent with the monotonicity of the table . Then j will always be between 0 and n inclusive a value of 0 indicates off-scale at one end of the table n indicates off-scale at the other end. In most cases when all is said and done it is hard to do better than bisection which will find the right place in the table in about log2n tries. We already did use bisection in the spline evaluation routine splint of the preceding section so you might glance back at that. Standing by itself a bisection routine looks like this void locate float xx unsigned long n float x unsigned long j Given an array xx and given a value x returns a value j such that x is between xx j and xx j 1 . xx must be monotonic either increasing or decreasing. j 0 or j n is returned to indicate that x is out of range. unsigned long ju jm jl int ascnd Initialize lower and upper limits. If we are not yet done compute a midpoint jl 0 ju n 1 ascnd xx n xx 1 while ju-jl 1 jm ju jl 1 if x xx jm ascnd jl jm and replace either the lower limit else ju jm if x xx 1 j 1 else if x xx n j n-1 else j jl or the upper limit as .
