ISRCH

Searches a sorted integer vector for a given integer and return its index.

Required Arguments

IVALUE — Scalar to be searched for in IY. (Input)

IX — Vector of length N * INCX. (Input)
IY is obtained from IX for I = 1, 2, …, N by IY(I) = IX(1 + (I ‑ 1) * INCX). IY(1), IY(2), …, IY(N) must be in ascending order.

INDEX — Index of IY pointing to IVALUE. (Output)
If INDEX is positive, IVALUE is found in IY. If INDEX is negative, IVALUE is not found in IY.

 

INDEX

Location of VALUE

1 thru N

IVALUE = IY(INDEX)

‑1

IVALUE < IY(1) or N = 0

‑N thru ‑2

IY(‑INDEX ‑ 1) < IVALUE < IY (‑ INDEX)

‑(N + 1)

IVALUE> Y(N)

Optional Arguments

N — Length of vector IY. (Input)
Default: N = size (IX,1) / INCX.

INCX — Displacement between elements of IX. (Input)
INCX must be greater than zero.
Default: INCX = 1.

FORTRAN 90 Interface

Generic: CALL ISRCH (IVALUE, IX, INDEX [, …])

Specific: The specific interface name is S_ISRCH.

FORTRAN 77 Interface

Single: CALL ISRCH (N, IVALUE, IX, INCX, INDEX)

Description

Routine ISRCH searches an integer vector x (stored in IX), whose n elements are sorted in ascending order for an integer c (stored in IVALUE). 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 IX, must be searched. The elements of row I are assumed to be in ascending order. Here, set INCX equal to the leading dimension of IX exactly as specified in the dimension statement in the calling program. With IX declared

INTEGER IX(LDIX,N)

the invocation

CALL ISRCH (VALUE, X(I, 1), INDEX, N=N, INCX=LDIX)

returns an index that will reference a column number of IX.

The routine ISRCH performs a binary search. The routine is an implementation of algorithm B discussed by Knuth (1973, pages 407‑411).

Example

This example searches an integer vector sorted in ascending order for the value 653. The problem is discussed by Knuth (1973, pages 407‑409).

 

USE ISRCH_INT

USE UMACH_INT

 

IMPLICIT NONE

INTEGER N

PARAMETER (N=16)

!

INTEGER INDEX, NOUT

INTEGER IVALUE, IX(N)

!

DATA IX/61, 87, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, &

703, 765, 897, 908/

!

IVALUE = 653

CALL ISRCH (IVALUE, IX, INDEX)

!

CALL UMACH (2, NOUT)

WRITE (NOUT,*) 'INDEX = ', INDEX

END

Output

 

INDEX = 11