SRCH
Searches a sorted vector for a given scalar and return its index.
Required Arguments
VALUE — Scalar to be searched for in Y. (Input)
X — Vector of length N * INCX. (Input)
Y is obtained from X for I = 1, 2, …, N by Y(I) = X(1 + (I ‑ 1) * INCX). Y(1), Y(2), …, Y(N) must be in ascending order.
INDEX — Index of Y pointing to VALUE. (Output)
If INDEX is positive, VALUE is found in Y. If INDEX is negative, VALUE is not found in Y.
|
INDEX |
Location of VALUE |
|
1 thru N |
VALUE = Y(INDEX) |
|
‑1 |
VALUE < Y(1) or N = 0 |
|
‑N thru ‑2 |
Y(‑INDEX ‑1) < VALUE < Y(‑INDEX) |
|
‑(N + 1) |
VALUE > Y(N) |
Optional Arguments
N — Length of vector Y. (Input)
Default: N = (size (X,1)) / INCX.
INCX — Displacement between elements of X. (Input)
INCX must be greater than zero.
Default: INCX = 1.
FORTRAN 90 Interface
Generic: CALL SRCH (VALUE, X, INDEX [, …])
Specific: The specific interface names are S_SRCH and D_SRCH.
FORTRAN 77 Interface
Single: CALL SRCH (N, VALUE, X, INCX, INDEX)
Double: The double precision name is DSRCH.
Description
Routine SRCH searches a real vector x (stored in X), whose n elements are sorted in ascending order for a real number c (stored in VALUE). If c is found in x, its index i (stored in INDEX) is returned so that xi = c. Otherwise, a negative number i is returned for the index. Specifically,
|
if 1 ≤ i ≤ n |
then xi = c |
|
if i = ‑1 |
then c < x1 or n = 0 |
|
if ‑ n ≤ I ≤ ‑ 2 |
then x–i–1 < c < x– i |
|
if i = ‑(n + 1) |
then c > xn |
The argument INCX is useful if a row of a matrix, for example, row number I of a matrix X, must be searched. The elements of row I are assumed to be in ascending order. In this case, set INCX equal to the leading dimension of X exactly as specified in the dimension statement in the calling program. With X declared
REAL X(LDX,N)
the invocation
CALL SRCH (N, VALUE, X(I,1), LDX, INDEX)
returns an index that will reference a column number of X.
Routine SRCH performs a binary search. The routine is an implementation of algorithm B discussed by Knuth (1973, pages 407‑411).
Example
This example searches a real vector sorted in ascending order for the value 653.0. The problem is discussed by Knuth (1973, pages 407‑409).
USE SRCH_INT
USE UMACH_INT
IMPLICIT NONE
INTEGER N
PARAMETER (N=16)
!
INTEGER INDEX, NOUT
REAL VALUE, X(N)
!
DATA X/61.0, 87.0, 154.0, 170.0, 275.0, 426.0, 503.0, 509.0, &
512.0, 612.0, 653.0, 677.0, 703.0, 765.0, 897.0, 908.0/
!
VALUE = 653.0
CALL SRCH (VALUE, X, INDEX)
!
CALL UMACH (2, NOUT)
WRITE (NOUT,*) 'INDEX = ', INDEX
END
INDEX = 11
