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 (N, IVALUE, IX(I,1), LDIX, INDEX)

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

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