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

Output

 

INDEX =   11

Visual Numerics, Inc. Visual Numerics - Developers of IMSL and PV-WAVE http://www.vni.com/ PHONE: 713.784.3131 FAX:713.781.9260