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.

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.

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.

Default: N = (size (X,1)) / INCX.

INCX — Displacement between elements of X. (Input)

INCX must be greater than zero.

Default: INCX = 1.

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