Binary search with SEARCH ALL
A serial SEARCH looks at elements one at a time. In a 10,000-entry table,
a code near the end takes about 10,000 comparisons. SEARCH ALL does a
binary search instead: it checks the middle element, discards the half
that cannot contain the key, and repeats. 10,000 entries take at most 14
comparisons, and a million take 20.
The price is one strict rule: the table must be in key order.
IDENTIFICATION DIVISION.
PROGRAM-ID. BINDEMO.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 WS-STATE-VALUES.
05 FILLER PIC X(12) VALUE "CACalifornia".
05 FILLER PIC X(12) VALUE "FLFlorida ".
05 FILLER PIC X(12) VALUE "NYNew York ".
05 FILLER PIC X(12) VALUE "TXTexas ".
05 FILLER PIC X(12) VALUE "WAWashington".
01 WS-STATE-TABLE REDEFINES WS-STATE-VALUES.
05 WS-STATE OCCURS 5 TIMES
ASCENDING KEY IS WS-ST-CODE
INDEXED BY ST-IX.
10 WS-ST-CODE PIC X(2).
10 WS-ST-NAME PIC X(10).
01 WS-WANTED PIC X(2).
PROCEDURE DIVISION.
MOVE "TX" TO WS-WANTED
PERFORM 1000-FIND-STATE
MOVE "OH" TO WS-WANTED
PERFORM 1000-FIND-STATE
STOP RUN.
1000-FIND-STATE.
SEARCH ALL WS-STATE
AT END
DISPLAY WS-WANTED " NOT FOUND"
WHEN WS-ST-CODE(ST-IX) = WS-WANTED
DISPLAY WS-WANTED " IS " WS-ST-NAME(ST-IX)
END-SEARCH.
Output:
TX IS Texas
OH NOT FOUND
What is different from SEARCH
SEARCH |
SEARCH ALL |
|
|---|---|---|
| Table order | Any | Must be sorted on the key |
| Declaration | INDEXED BY |
INDEXED BY and ASCENDING KEY (or DESCENDING KEY) |
SET index first |
Yes, always | No, it manages the index itself |
WHEN clauses |
Any number, any condition | One, testing the key with = (several keys can be joined with AND) |
| Speed on big tables | Slow | Fast |
The WHEN must compare the key field (subscripted by the table's
index) for equality. You cannot write WHEN WS-ST-NAME(ST-IX) = ..., because
the table is not sorted by name, or use >, because binary search is only
defined for exact matches.
What happens if the table is not sorted
The compiler cannot check the order: ASCENDING KEY is a promise from you.
Swap Texas and California in the table above, so it starts TX, FL,
NY, CA, WA, and search for TX. The program now prints
TX NOT FOUND, although TX is the very first entry. The binary search
looked at the middle (NY), decided TX must be in the upper half, and
never went back to the start. Other codes, such as NY, are still found,
so the bug appears only for some keys.
Sorting is your job
For a hard-coded table, type it in order and leave a comment saying so.
For a table loaded from a file, sort the file first (a SORT step in the
JCL, or the COBOL SORT verb) or check the order as you load and stop
the job if a key is out of sequence.
On the job
Tables loaded from input usually hold fewer rows than their OCCURS
maximum. Unused slots at the end must not break the key order, so shops
fill them with HIGH-VALUES (for ascending keys) before loading, or use
OCCURS DEPENDING ON so the search stops at the real count. That is
covered in a later lesson.
Your task
The bureau de change converts euros into other currencies. The starter has a hard-coded rate table, sorted by currency code, giving units of each currency per 1 EUR:
| Code | Rate | Code | Rate |
|---|---|---|---|
| AUD | 1.6500 | JPY | 160.2500 |
| CAD | 1.4800 | NOK | 11.7000 |
| CHF | 0.9400 | SEK | 11.2000 |
| GBP | 0.8500 | USD | 1.0800 |
Read requests, one per line, until END. Each request is a 3-character
currency code followed by a euro amount as 9(7)V99 (9 digits, 2 implied
decimals). USD000015000 means "convert 150.00 EUR to USD".
For each request display the conversion, with the result rounded to
the cent, or UNKNOWN CURRENCY:
150.00 EUR = 162.00 USD
XYZ UNKNOWN CURRENCY
Declare the table's key and index (ASCENDING KEY IS WS-CCY,
INDEXED BY CCY-IX) and use SEARCH ALL. Use WS-EUR-OUT and
WS-CONV-OUT for formatting.