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 IVALUE |
|
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
INDEX = 11
