Engineering and Scientific Subroutine Library for AIX Version 3 Release 3: Guide and Reference

IBSRCH, SBSRCH, and DBSRCH--Binary Search for Elements of a Sequence X in a Sorted Sequence Y

These subroutines perform a binary search for the locations of the elements of sequence x in another sequence y, where y has been sorted into ascending order. The first occurrence of each element is found. When an exact match is not found, the position of the next larger element in y is indicated. The locations are returned in the indices array INDX, and, optionally, return codes indicating whether the exact elements were found are returned in array RC.

Table 152. Data Types

x, y	Subroutine
Integer	IBSRCH
Short-precision real	SBSRCH
Long-precision real	DBSRCH

Syntax

Fortran	CALL IBSRCH \| SBSRCH \| DBSRCH (`x`, `incx`, `n`, `y`, `incy`, `m`, `indx`, `rc`, `iopt`)
C and C++	ibsrch \| sbsrch \| dbsrch (`x`, `incx`, `n`, `y`, `incy`, `m`, `indx`, `rc`, `iopt`);
PL/I	CALL IBSRCH \| SBSRCH \| DBSRCH (`x`, `incx`, `n`, `y`, `incy`, `m`, `indx`, `rc`, `iopt`);

On Entry

x

is the sequence x of length n, containing the elements for which sequence y is searched. Specified as: a one-dimensional array, containing numbers of the data type indicated in Table 152. It must have at least 1+(n-1)|incx| elements.

incx

is the stride for sequence x. Specified as: a fullword integer. It can have any value.

n

is the number of elements in sequence x and arrays INDX and RC. Specified as: a fullword integer; n >= 0.

y

is the sequence y of length m, to be searched, where y must be sorted into ascending order.

Note:: Be careful in specifying the stride for sequence y. A negative stride reverses the direction of the search, because the order of the sequence elements is reversed in the array.

Specified as: a one-dimensional array of (at least) length 1+(m-1)|incy|, containing numbers of the data type indicated in Table 152.

incy

is the stride for sequence y. Specified as: a fullword integer. It can have any value.

m

is the number of elements in sequence y. Specified as: a fullword integer; m >= 0.

indx

See On Return.

rc

See On Return.

iopt

has the following meaning, where:

If iopt = 0, the rc argument is not used in the computation.

If iopt = 1, the rc argument is used in the computation.

Specified as: a fullword integer; iopt = 0 or 1.

On Return

indx

is the array, referred to as INDX, containing the n indices that indicate the positions of the elements of sequence x in sequence y. The first occurrence of the element found in sequence y is indicated in array INDX. When an exact match between an element of sequence x and an element of sequence y is not found, the position of the next larger element in sequence y is indicated. When the element in sequence x is larger than all the elements in sequence y, then m+1 is indicated in array INDX.

Returned as: a one-dimensional array of length n, containing fullword integers; 1 <= (INDX elements) <= m+1.

rc

has the following meaning, where:

If iopt = 0, then rc is not used, and its contents remain unchanged.

If iopt = 1, it is the array, referred to as RC, containing the n return codes that indicate whether the elements in sequence x were found in sequence y. For i = 1, n, elements RC(i) = 0 if x_i matches an element in sequence y, and RC(i) = 1 if an exact match is not found in sequence y.

Returned as: a one-dimensional array of length n, containing fullword integers; RC(i) = 0 or 1.

Notes

The elements of y must be sorted into ascending order; otherwise, results are unpredictable. For details on how to do this, see ISORT, SSORT, and DSORT--Sort the Elements of a Sequence.
If you do not need the results provided in array RC by these subroutines, you get better performance if you do not request it. That is, specify 0 for the iopt argument.

Function

These subroutines perform a binary search for the first occurrence (or last occurrence, using negative stride) of the locations of the elements of sequence x in another sequence y, where y must be sorted into ascending order before calling this subroutine. The first occurrence of each element is found. Two arrays are returned, containing the results of the binary searches:

INDX, the indices array, contains the positions of the elements of sequence x in sequence y. When an exact match between values of elements in sequences x and y is not found, the location of the next larger element in sequence y is indicated in array INDX.
RC, the return codes array, indicates for each element in sequence x whether the exact element was found in sequence y. If you do not need these results, you get better performance if you set iopt = 0.

The results returned for the INDX and RC arrays are expressed as follows:

For i = 1, n

for all y_j >= x_i, j = 1, m , INDX(i) = min(j)

if all y_j < x_i, j = 1, m , INDX(i) = m+1

And for i = 1, n

if x_i = y_INDX(i), RC(i) = 0

if x_i <> y_INDX(i), RC(i) = 1

where:

x is a sequence of length n, containing the search elements.

y is a sequence of length m to be searched. It must be sorted into ascending order.

INDX is the array of length n of indices.

RC is the array of length n of return codes.

See reference [75]. If n is 0, no search is performed. If m is 0, then:

INDX(i) = 1 and RC(i) = 1 for i = 1, n

It is important to note that a negative stride for sequence y reverses the direction of the search, because the order of the sequence elements is reversed in the array. For more details on sorting sequences, see Function.

Error Conditions

Computational Errors

None

Input-Argument Errors

n < 0
m < 0
iopt <> 0 or 1

Example 1

This example shows a search where sequences x and y have positive strides, and where the optional return codes are returned as part of the output.

Call Statement and Input

             X  INCX  N   Y  INCY  M    INDX   RC  IOPT
             |   |    |   |   |    |     |     |    |
CALL IBSRCH( X , 2  , 5 , Y , 1  , 10 , INDX , RC , 1 )
 
X        =  (-3, . , 125, . , 30, . , 20, . , 70)
Y        =  (10, 20, 30, 30, 40, 50, 60, 80, 90, 100)

Output

INDX     =  (1, 11, 3, 2, 8)
RC       =  (1, 1, 0, 0, 1)

Example 2

This example shows the same calling sequence as in Example 1, except that it includes the IOPT argument, specified as 1. This is equivalent to using the calling sequence in Example 1 and gives the same results.

Call Statement and Input

             X  INCX  N   Y  INCY  M    INDX   RC  IOPT
             |   |    |   |   |    |     |     |    |
CALL IBSRCH( X , 2  , 5 , Y , 1  , 10 , INDX , RC , 1  )

Example 3

This example shows a search where sequence x has a negative stride, and sequence y has a positive stride. The optional return codes are not requested, because IOPT is specified as 0.

Call Statement and Input

             X   INCX  N   Y  INCY  M    INDX   RC  IOPT
             |    |    |   |   |    |     |     |    |
CALL IBSRCH( X , -2  , 5 , Y , 1  , 10 , INDX , RC , 0 )
 
X        =  (-3, . , 125, . , 30, . , 20, . , 70)
Y        =  (10, 20, 30, 30, 40, 50, 60, 80, 90, 100)

Output

INDX     =  (8, 2, 3, 11, 1)
RC       =(not relevant)

Example 4

This example shows a search where sequence x has a positive stride, and sequence y has a negative stride. As shown below, elements of y are in descending order in array Y. The optional return codes are not requested, because IOPT is specified as 0.

Call Statement and Input

             X  INCX  N   Y   INCY  M    INDX   RC  IOPT
             |   |    |   |    |    |     |     |    |
CALL IBSRCH( X , 2  , 5 , Y , -1  , 10 , INDX , RC , 0  )

X = (-3, . , 125, . , 30, . , 20, . , 70)
Y = (100, 90, 80, 60, 50, 40, 30, 30, 20, 10)
RC =(not relevant)

Output

INDX     =  (1, 11, 3, 2, 8)

[ Top of Page | Previous Page | Next Page | Table of Contents | Index ]