SEARCH ALL

SEARCH ALL is the same statement as SEARCH with one promise added: the table is sorted on the key, so the verb can halve the range on every comparison instead of walking it. The promise is the program's, and nothing checks it.

SEARCH ALL and a sorted key

The table declares which entry is the key, with ASCENDING KEY IS after the OCCURS. The search then has one WHEN that compares the key:

IDENTIFICATION DIVISION. PROGRAM-ID. SALL. DATA DIVISION. WORKING-STORAGE SECTION. 01 CODES-T. 05 CODE-E PIC X(3) OCCURS 6 TIMES ASCENDING KEY IS CODE-E INDEXED BY IDX. 01 SEEK-F PIC X(3) VALUE "D40". PROCEDURE DIVISION. MOVE "A10" TO CODE-E(1). MOVE "B20" TO CODE-E(2). MOVE "C30" TO CODE-E(3). MOVE "D40" TO CODE-E(4). MOVE "E50" TO CODE-E(5). MOVE "F60" TO CODE-E(6). SET IDX TO 1. SEARCH ALL CODE-E AT END DISPLAY "code " SEEK-F " not found" WHEN CODE-E(IDX) = SEEK-F DISPLAY "code " SEEK-F " at entry " IDX END-SEARCH. MOVE "C35" TO SEEK-F. SEARCH ALL CODE-E AT END DISPLAY "code " SEEK-F " not found" WHEN CODE-E(IDX) = SEEK-F DISPLAY "code " SEEK-F " at entry " IDX END-SEARCH. STOP RUN.

cobc -x -free -Wall -o sall sall.cob
./sall

code D40 at entry +000000004
code C35 not found

A key that is in the table

The entries are in ascending order, the key is the whole entry, and the search reports the fourth. A binary search over six entries compares the third and then the fourth, where the walk of SEARCH would compare four entries; over a table of a thousand the difference is ten comparisons against five hundred.

The clause takes one or more keys. This compiler accepts several with ASCENDING KEY IS A B and searches on the first; the keys after the first make the sort order total but do not change which entry is found, so a program with duplicate first keys is the case to think about before adding them.

A key that is not

A key between two entries, C35 between C30 and D40, takes the AT END branch in the same way as in the serial search. The index ends on an entry that is not a match, and its value is not the number of entries plus one as it was with SEARCH: a binary search stops where the range became empty, which is wherever the last comparison happened to be.

That is the reason a program reads the table after SEARCH ALL only when a match was found. The index is a position when the search succeeds and a leftover when it does not.

The WHEN of a SEARCH ALL must compare the key for equality. A range condition is refused at build time with invalid SEARCH ALL condition, because the halving only works on an equality test; the lesson on SEARCH has the shape a range needs.

An unsorted table

Nothing in the compiler or the runtime checks that the table is sorted. The same six codes in the opposite order make both keys that are present report as missing:

IDENTIFICATION DIVISION. PROGRAM-ID. UNSORTED. DATA DIVISION. WORKING-STORAGE SECTION. 01 CODES-T. 05 CODE-E PIC X(3) OCCURS 6 TIMES ASCENDING KEY IS CODE-E INDEXED BY IDX. 01 SEEK-F PIC X(3) VALUE "A10". PROCEDURE DIVISION. MOVE "F60" TO CODE-E(1). MOVE "E50" TO CODE-E(2). MOVE "D40" TO CODE-E(3). MOVE "C30" TO CODE-E(4). MOVE "B20" TO CODE-E(5). MOVE "A10" TO CODE-E(6). SET IDX TO 1. SEARCH ALL CODE-E AT END DISPLAY "code " SEEK-F " not found" WHEN CODE-E(IDX) = SEEK-F DISPLAY "code " SEEK-F " at entry " IDX END-SEARCH. MOVE "F60" TO SEEK-F. SEARCH ALL CODE-E AT END DISPLAY "code " SEEK-F " not found" WHEN CODE-E(IDX) = SEEK-F DISPLAY "code " SEEK-F " at entry " IDX END-SEARCH. STOP RUN.

cobc -x -free -Wall -o unsorted unsorted.cob
./unsorted

code A10 not found
code F60 not found

Both codes are in the table, at the first and the sixth entry, and the program says both are missing. The build printed no warning; the compiler cannot know the order of values the program will store at run time.

The rule this leaves is the one every binary search carries: sort the table before SEARCH ALL and keep it sorted on every write, or use SEARCH and pay the comparisons. The next lesson puts a table inside a table, where the same rule applies to each dimension.

Exercises

  1. Sort the unsorted program by hand, run it again, and count how many WHEN comparisons each key needs.
  2. Search the sorted table for A10 and for F60. Which entries does the binary search compare in each case?
  3. Make two entries equal and search for that key with SEARCH ALL. Which entry is found?
  4. Write a paragraph that checks a table is in ascending order before a SEARCH ALL and sets a flag when it is not.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does SEARCH ALL require that SEARCH does not?

    Answer

    A sorted table and a key declared with ASCENDING KEY

    The binary search halves the range on each comparison, which is only valid on sorted data.

  2. How many comparisons does SEARCH ALL make on a table of a thousand entries?

    Answer

    About ten, because it halves the range each time

    Ten halvings cover a thousand entries, against the walk of a serial search.

  3. What happens when the table is not sorted?

    Answer

    The search can report a key that is present as missing, with no warning

    The unsorted run reported both A10 and F60 as missing although both were in the table.

  4. Where is the index after an unsuccessful SEARCH ALL?

    Answer

    Wherever the last comparison happened, not past the table

    The binary search stops when the range is empty, so the leftover position is not the count.

  5. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q5. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC X(2) OCCURS 4 TIMES ASCENDING KEY IS E-F INDEXED BY I. 01 K-F PIC X(2) VALUE "CC". PROCEDURE DIVISION. MOVE "AA" TO E-F(1). MOVE "BB" TO E-F(2). MOVE "CC" TO E-F(3). MOVE "DD" TO E-F(4). SET I TO 1. SEARCH ALL E-F AT END DISPLAY "missing" WHEN E-F(I) = K-F DISPLAY "at " I END-SEARCH. STOP RUN.

    Answer

    at +000000003

    CC is the third entry of the sorted table, and the index prints in its signed form.

  6. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q6. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC X(2) OCCURS 4 TIMES ASCENDING KEY IS E-F INDEXED BY I. 01 K-F PIC X(2) VALUE "EE". PROCEDURE DIVISION. MOVE "AA" TO E-F(1). MOVE "BB" TO E-F(2). MOVE "CC" TO E-F(3). MOVE "DD" TO E-F(4). SET I TO 1. SEARCH ALL E-F AT END DISPLAY "missing" WHEN E-F(I) = K-F DISPLAY "found" END-SEARCH. STOP RUN.

    Answer

    missing

    EE is past every entry in the sorted table, so the range empties and AT END runs.

  7. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q7. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC X(2) OCCURS 4 TIMES ASCENDING KEY IS E-F INDEXED BY I. 01 K-F PIC X(2) VALUE "AA". PROCEDURE DIVISION. MOVE "DD" TO E-F(1). MOVE "CC" TO E-F(2). MOVE "BB" TO E-F(3). MOVE "AA" TO E-F(4). SET I TO 1. SEARCH ALL E-F AT END DISPLAY "missing" WHEN E-F(I) = K-F DISPLAY "found" END-SEARCH. STOP RUN.

    Answer

    missing

    The table is in descending order, so the binary search never looks at the last entry where AA sits.

  8. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q8. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC 9(2) OCCURS 3 TIMES ASCENDING KEY IS E-F INDEXED BY I. 01 S-F PIC 9(3) VALUE 0. PROCEDURE DIVISION. MOVE 10 TO E-F(1). MOVE 20 TO E-F(2). MOVE 30 TO E-F(3). SET I TO 1. SEARCH ALL E-F AT END DISPLAY "none" WHEN E-F(I) = 20 MOVE E-F(I) TO S-F END-SEARCH. DISPLAY S-F. STOP RUN.

    Answer

    020

    The binary search stops on the entry equal to the key and the program copies it into the total.

  9. A table is filled from a file and then searched with SEARCH ALL, but the file is not in key order. What does the program do?

    Answer

    It may report keys that exist as missing, and nothing warns

    That is exactly the unsorted run on this page: both present keys were reported missing.

  10. Which search keeps working when the table is not sorted?

    Answer

    SEARCH, which compares every entry in turn

    A serial search does not rely on the order, so it finds the entry wherever it sits.

The code on this page was built with cobc (GnuCOBOL) 3.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev