Interpolation.BisectionLocate Method 

This is a utility function which searches an monotonic sequence (with increasing or decreasing elements) using the bisection method and returns the relative position within the sequence.

Parameters

monotonicSequence

An array of monotonic values which may be increasing or decreasing.

valueBeingOrdered

The point (or value) for which its order is being evaluated.

Remarks

We offer this method as an auxiliary method since though sorting algorithms are strictly speaking not part of Interpolation or Extrapolation theory these methods are often required such methods. Here we implement what is known as the bisection method which will find the right place in about log2 n tries, where n is the number of elements in the monotonic sequence. To summaries the bisection algorithm is an ideal sorting algorithm to use here and can only marginally be improved in particular cases and most importantly it is sufficiently fast in all practical instances which we have encountered.

This method attempts to bracket the valueBeingOrdered parameter between two consecutive elements of the array and return the lower bound. Several special cases are treated separately as follows:

• If the array is null, an InterpolationException is thrown.
• If the array is empty, this method will always return zero.
• If the value being ordered equals the first elements within the array, this method will always return the position of the first element.
• If the value being ordered equals all elements within the array, this method will always return the position of the first element.
• If the value being ordered equals the last elements within the array, this method will always return the position of the penultimate element, unless one of the previous situations occurs.
• If the value being ordered equals consecutive elements inside the array, located neither at the beginning or end of the array, this method will return the position of the last consecutive element for an array of increasing values or the position of the element before the first consecutive element for an array of decreasing values.
• If the value being ordered is outside the range of the array, this method will either return -1 if the value should be ordered before the first element or the position of the last element if the value should be ordered after the last element.

Exceptions

See Also

Interpolation Class | Interpolation Namespace