[an error occurred while processing this directive]

HP OpenVMS Systems Documentation

HP COBOL
User Manual

When you vary an index associated with a table other than the one you are searching, the controlling index is the first index you specify in the INDEXED BY phrase of the table you are searching. Each time the controlling index is incremented, the index you specify in the VARYING phrase is incremented. In this manner, you can search two tables in synchronization. Example 4-18 and Example 4-22 show how to vary an index associated with a table other than the one you are searching.

When you omit the VARYING phrase, the first index you specify in the INDEXED BY phrase becomes the controlling index. Only this index is incremented during a serial search. Example 4-18 and Example 4-23 show how to perform a serial search without using the VARYING phrase.

4.3.8.2 Implementing a Binary Search

You can use the SEARCH statement to perform a nonsequential (binary) table search.

To perform a binary search, you must specify an index name in the INDEXED BY phrase and a search key in the KEY IS phrase of the OCCURS clause of the table being searched.

A binary search depends on the ASCENDING/DESCENDING KEY attributes. If you specify an ASCENDING KEY, the data in the table must either be stored in ascending order or sorted in ascending order prior to the search. For a DESCENDING KEY, data must be stored or sorted in descending order prior to the search.

On Alpha and I64 systems, you can sort an entire table in preparation for a binary search. Use the SORT statement (Format 2, an HP extension), described in the HP COBOL Reference Manual. <>

During a binary search, the first (or only) index you specify in the INDEXED BY phrase of the OCCURS clause of the table being searched is the controlling index. You do not have to initialize an index in a binary search because index manipulation is automatic.

In addition to being generally faster than a sequential search, a binary search allows multiple equality checks.

The following search sequence lists the capabilities of a binary search. At program execution time, the system:

Examines the range of permissible index values, selects the median value, and assigns this value to the index.
Checks for equality in WHEN and AND clauses.
Terminates the search if all equality statements are true. If you use the imperative statement after the final equality clause, that statement executes; otherwise, program control passes to the next procedural sentence, the search exits, and the index retains its current value.
Takes the following actions if the equality test of a table element is false:
1. Executes the imperative statement associated with the AT END statement (if present) when all table elements have been tested. If there is no AT END statement, program control passes to the next procedural statement.
2. Determines which half of the table is to be eliminated from further consideration. This is based on whether the key being tested was specified as ASCENDING or DESCENDING and whether the test failed because of a greater-than or less-than comparison. For example, if the key values are stored in ascending order, and the median table element being tested is greater than the value of the argument, then all key elements following the one being tested must also be greater. Therefore, the upper half of the table is removed from further consideration and the search continues at the median point of the lower half.
3. Begins processing all over again at Step 1.

A useful variation of the binary search is that of specifying multiple search keys. Multiple search keys allow you to select a specified table element from among several elements that have duplicate low-order keys. An example is a telephone listing where several people have the same last and first names, but different middle initials. All specified keys must be either ascending or descending. Example 4-24 shows how to use multiple search keys.

The table in Example 4-18 is followed by several examples (Examples 4-19, 4-20, 4-21, 4-22, and 4-23) of how to search it.

Example 4-18 Sample Table

DATA DIVISION.
WORKING-STORAGE SECTION.
01  TEMP-IND                            USAGE IS INDEX.
01  FED-TAX-TABLES.
    02  ALLOWANCE-DATA.
        03  FILLER                      PIC X(70) VALUE
            "0101440
-           "0202880
-           "0304320
-           "0405760
-           "0507200
-           "0608640
-           "0710080
-           "0811520
-           "0912960
-           "1014400".
    02  ALLOWANCE-TABLE REDEFINES ALLOWANCE-DATA.
        03  FED-ALLOWANCES OCCURS 10 TIMES
            ASCENDING KEY IS ALLOWANCE-NUMBER
            INDEXED BY IND-1.
            04  ALLOWANCE-NUMBER        PIC XX.
            04  ALLOWANCE               PIC 99999.

    02 SINGLES-DEDUCTION-DATA.
        03  FILLER                      PIC X(112) VALUE
            "0250006700000016
-           "0670011500067220
-           "1150018300163223
-           "1830024000319621
-           "2400027900439326
-           "2790034600540730
-           "3460099999741736".
   02   SINGLE-DEDUCTION-TABLE REDEFINES SINGLES-DEDUCTION-DATA.
        03  SINGLES-TABLE OCCURS 7 TIMES
            ASCENDING KEY IS S-MIN-RANGE S-MAX-RANGE
            INDEXED BY IND-2, TEMP-INDEX.
            04  S-MIN-RANGE             PIC 99999.
            04  S-MAX-RANGE             PIC 99999.
            04  S-TAX                   PIC 9999.
            04  S-PERCENT               PIC V99.

    02  MARRIED-DEDUCTION-DATA.
        03  FILLER                      PIC X(119) VALUE
            "04800096000000017
-           "09600173000081620
-           "17300264000235617
-           "26400346000390325
-           "34600433000595328
-           "43300500000838932
-           "50000999991053336".
    02  MARRIED-DEDUCTION-TABLE REDEFINES MARRIED-DEDUCTION-DATA.
        03 MARRIED-TABLE OCCURS 7 TIMES
           ASCENDING KEY IS M-MIN-RANGE M-MAX-RANGE
           INDEXED BY IND-0, IND-3.
           04  M-MIN-RANGE              PIC 99999.
           04  M-MAX-RANGE              PIC 99999.
           04  M-TAX                    PIC 99999.
           04  M-PERCENT                PIC V99.

Example 4-19 shows how to perform a serial search.

Example 4-19 A Serial Search

01   TAXABLE-INCOME PIC 9(6) VALUE 50000.
01   FED-TAX-DEDUCTION PIC 9(6).
PROCEDURE DIVISION.
BEGIN.
       PERFORM SINGLE.
       DISPLAY FED-TAX-DEDUCTION.
       STOP RUN.
SINGLE.
       IF TAXABLE-INCOME < 02500
               GO TO END-FED-COMP.
       SET IND-2 TO 1.
       SEARCH SINGLES-TABLE AT END
               GO TO TABLE-2-ERROR
          WHEN TAXABLE-INCOME = S-MIN-RANGE(IND-2)
               MOVE S-TAX(IND-2) TO FED-TAX-DEDUCTION
          WHEN TAXABLE-INCOME < S-MAX-RANGE(IND-2)
               COMPUTE FED-TAX-DEDUCTION =
                   S-TAX(IND-2) + (TAXABLE-INCOME - S-TAX(IND-2)) *
                   S-PERCENT(IND-2).
   .
   .
   .

Example 4-20 shows how to use SEARCH while varying an index other than the first index.

Example 4-20 Using SEARCH and Varying an Index Other than the First Index

01   TAXABLE-INCOME PIC 9(6) VALUE 50000.
01   FED-TAX-DEDUCTION PIC 9(6).
PROCEDURE DIVISION.
BEGIN.
       PERFORM MARRIED.
       DISPLAY FED-TAX-DEDUCTION.
       STOP RUN.
MARRIED.
       IF TAXABLE-INCOME < 04800
               MOVE ZEROS TO FED-TAX-DEDUCTION
               GO TO END-FED-COMP.
       SET IND-3 TO 1.
       SEARCH MARRIED-TABLE VARYING IND-3 AT END
               GO TO TABLE-3-ERROR
          WHEN TAXABLE-INCOME = M-MIN-RANGE(IND-3)
               MOVE M-TAX(IND-3) TO FED-TAX-DEDUCTION
          WHEN TAXABLE-INCOME < M-MAX-RANGE(IND-3)
               COMPUTE FED-TAX-DEDUCTION =
                   M-TAX(IND-3) + (TAXABLE-INCOME - M-TAX(IND-3)) *
                   M-PERCENT(IND-3).
   .
   .
   .

Example 4-21 shows how to use SEARCH while varying an index data item.

Example 4-21 Using SEARCH and Varying an Index Data Item

01   TAXABLE-INCOME PIC 9(6) VALUE 50000.
01   FED-TAX-DEDUCTION PIC 9(6).
PROCEDURE DIVISION.
BEGIN.
       PERFORM SINGLE.
       DISPLAY FED-TAX-DEDUCTION.
       STOP RUN.
SINGLE.
       IF TAXABLE-INCOME < 02500
               GO TO END-FED-COMP.
       SET IND-2 TO 1.
       SEARCH SINGLES-TABLE VARYING TEMP-IND AT END
               GO TO TABLE-2-ERROR
          WHEN TAXABLE-INCOME = S-MIN-RANGE(IND-2)
               MOVE S-TAX(IND-2) TO FED-TAX-DEDUCTION
          WHEN TAXABLE-INCOME < S-MAX-RANGE(IND-2)
               MOVE S-TAX(IND-2) TO FED-TAX-DEDUCTION
               SUBTRACT S-MIN-RANGE(IND-2) FROM TAXABLE-INCOME
               MULTIPLY TAXABLE-INCOME BY S-PERCENT(IND-2) ROUNDED
               ADD TAXABLE-INCOME TO FED-TAX-DEDUCTION.
   .
   .
   .

Example 4-22 shows how to use SEARCH while varying an index not associated with the target table.

Example 4-22 Using SEARCH and Varying an Index not Associated with the Target Table

01   TAXABLE-INCOME PIC 9(6) VALUE 50000.
01   FED-TAX-DEDUCTION PIC 9(6).
PROCEDURE DIVISION.
BEGIN.
       PERFORM SINGLE.
       DISPLAY FED-TAX-DEDUCTION.
       STOP RUN.
SINGLE.
        IF TAXABLE-INCOME < 02500
               GO TO END-FED-COMP.
        SET IND-2 TO 1.
        SEARCH SINGLES-TABLE VARYING IND-0 AT END
               GO TO TABLE-2-ERROR
          WHEN TAXABLE-INCOME = S-MIN-RANGE(IND-2)
               MOVE S-TAX(IND-2) TO FED-TAX-DEDUCTION

          WHEN TAXABLE-INCOME < S-MAX-RANGE(IND-2)
               MOVE S-TAX(IND-2) TO FED-TAX-DEDUCTION
               SUBTRACT S-MIN-RANGE(IND-2) FROM TAXABLE-INCOME
               MULTIPLY TAXABLE-INCOME BY S-PERCENT(IND-2) ROUNDED
               ADD TAXABLE-INCOME TO FED-TAX-DEDUCTION.
   .
   .
   .

Example 4-23 shows how to perform a serial search without using the VARYING phrase.

Example 4-23 Doing a Serial Search Without Using the VARYING Phrase

01   NR-DEPENDENTS     PIC 9(2)  VALUE 3.
01   GROSS-WAGE        PIC 9(6)  VALUE 50000.
01   TAXABLE-INCOME    PIC 9(6)  VALUE 50000.
01   FED-TAX-DEDUCTION PIC9(6).
01   MARITAL-STATUS    PIC X     VALUE "M".
PROCEDURE DIVISION.
BEGIN.
       PERFORM FED-DEDUCT-COMPUTATION.
       DISPLAY TAXABLE-INCOME.
       STOP RUN.
FED-DEDUCT-COMPUTATION.
          SET IND-1 TO 1.
          SEARCH FED-ALLOWANCES AT END
                 GO TO TABLE-1-ERROR
            WHEN ALLOWANCE-NUMBER(IND-1) = NR-DEPENDENTS
                 SUBTRACT ALLOWANCE(IND-1) FROM GROSS-WAGE
                     GIVING TAXABLE-INCOME ROUNDED.
          IF MARITAL-STATUS = "M"
                 GO TO MARRIED.
MARRIED.
   .
   .
   .

Example 4-24 shows how to perform a multiple-key, binary search.

Example 4-24 A Multiple-Key, Binary Search

IDENTIFICATION DIVISION.
PROGRAM-ID. MULTI-KEY-SEARCH.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 DIRECTORY-TABLE.
   05 NAMES-NUMBERS.
      10 FILLER                PIC X(30)
         VALUE "SMILEY    HAPPY     T.213-4332".
      10 FILLER                PIC X(30)
         VALUE "SMITH     ALAN      C.881-4987".
      10 FILLER                PIC X(30)
         VALUE "SMITH     CHARLES   J.345-2398".
      10 FILLER                PIC X(30)
         VALUE "SMITH     FREDERICK   745-0223".
      10 FILLER                PIC X(30)
         VALUE "SMITH     HARRY     C.573-3306".
      10 FILLER                PIC X(30)
         VALUE "SMITH     HARRY     J.295-3485".
      10 FILLER                PIC X(30)
         VALUE "SMITH     LARRY     X.976-5504".
      10 FILLER                PIC X(30)
         VALUE "SMITHWOOD ALBERT    J.349-9927".
   05 PHONE-DIRECTORY-TABLE REDEFINES NAMES-NUMBERS OCCURS 8 TIMES
                                  ASCENDING KEY IS LAST-NAME
                                                   FIRST-NAME
                                                   MID-INIT
                                  INDEXED BY DIR-INDX.
         15 LAST-NAME          PIC X(10).
         15 FIRST-NAME         PIC X(10).
         15 MID-INIT           PIC XX.
         15  PHONE-NUM         PIC X(8).
PROCEDURE DIVISION.
MULTI-KEY-BINARY-SEARCH.
    SEARCH ALL PHONE-DIRECTORY-TABLE
           WHEN LAST-NAME(DIR-INDX) = "SMITH"
           AND FIRST-NAME(DIR-INDX) = "HARRY"
           AND MID-INIT(DIR-INDX) = "J."
               NEXT SENTENCE.
DISPLAY-RESULTS.
    DISPLAY LAST-NAME(DIR-INDX)","
            FIRST-NAME(DIR-INDX)
            MID-INIT(DIR-INDX) " "
            PHONE-NUM(DIR-INDX).

Contents

Index

HP OpenVMS Systems Documentation

HP COBOLUser Manual

4.3.8.2 Implementing a Binary Search

HP COBOL
User Manual