Search an array of abscissas

SEARCH AN ARRAY of ABSCISSAS

PROBLEM

Given an array of abscissas A.J, J=1,...,N, with the elements either monotically increasing or monotically decreasing, and given a number V, find an integer J such that V lies between A.J and A.Jp1, where Jp1=J+1.

ALGORITHM

Bisection (see binary search) will find the right place in the table about lgN tries.

IMPLEMENTATION

Unit: internal function

Global variables: ascending sequence of values A.1,...,A.N

Parameters: positive integer N, number V

Returns: a value J such that V is between A.J and A.Jp1, where Jp1=J+1. J=0 or J=N indicates that V is out of range.

LOCATE: procedure expose A.
parse arg N, V
L = 0; U = N + 1; Ascnd = (A.N >= A.1)
do while (U - L) > 1
  M = (U + L) % 2
  if (V >= A.M) = Ascnd then L = M
    else U = M
end
if V = A.1 then return 1
if V = A.N then return N - 1
return L

CONNECTIONS

Binary search
Sequential search
Sequential search without sentinel
Interpolation search
Search in associative arrays

Literature

Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in C : the art of scientific computing

- 2nd ed. University Press, Cambridge, 1992