SEARCH: a serial search
The lesson on subscripts searched a table with a loop and a flag. SEARCH is that loop as a statement: it walks an indexed table from the current position, stops on the condition the program names, and reports the failure in a branch of its own.
SEARCH and its two exits
A SEARCH names the table entry, takes any number of WHEN clauses and one AT END. Each pass tests the WHEN against the entry the index points at, and moves the index on by one:
IDENTIFICATION DIVISION.
PROGRAM-ID. SEARCH1.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 CODES-T.
05 CODE-E PIC X(3) OCCURS 5 TIMES INDEXED BY IDX.
01 SEEK-F PIC X(3) VALUE "C30".
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).
SET IDX TO 1.
SEARCH 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 "Z99" TO SEEK-F.
SET IDX TO 1.
SEARCH 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.
DISPLAY "index after the searches " IDX.
STOP RUN.
cobc -x -free -Wall -o search search.cob
./search
code C30 at entry +000000003
code Z99 not found
index after the searches +000000006
The index starts where the program put it. Each SET IDX TO 1 before a search is what makes the second search see the whole table rather than the part after the first match; a program that forgets it searches from wherever the last one stopped.
The index after a match
A successful search leaves the index on the entry it matched, and the program can read that entry, use the index for another table with the same length, or show it. A table with duplicate keys needs one more step before the next search:
IDENTIFICATION DIVISION.
PROGRAM-ID. DUPS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 WORDS-T.
05 WORD-E PIC X(2) OCCURS 6 TIMES INDEXED BY I.
01 SEEK-F PIC X(2) VALUE "BB".
PROCEDURE DIVISION.
MOVE "AA" TO WORD-E(1).
MOVE "BB" TO WORD-E(2).
MOVE "CC" TO WORD-E(3).
MOVE "BB" TO WORD-E(4).
MOVE "DD" TO WORD-E(5).
MOVE "EE" TO WORD-E(6).
SET I TO 1.
SEARCH WORD-E
AT END DISPLAY "not found"
WHEN WORD-E(I) = SEEK-F
DISPLAY "first match at " I
END-SEARCH.
SET I UP BY 1.
SEARCH WORD-E
AT END DISPLAY "no later match"
WHEN WORD-E(I) = SEEK-F
DISPLAY "next match at " I
END-SEARCH.
STOP RUN.
cobc -x -free -Wall -o dup dup.cob
./dup
first match at +000000002
next match at +000000004
Without the SET I UP BY 1 the second search began on the entry the first one had already matched, and the program reported first match at 2 twice. That is what the index after a match means: a position, not a record of a match.
AT END and the index past the table
A search that runs off the end takes the AT END branch and leaves the index at the number of entries plus one: six for a table of five in the first run. The index is then invalid for a read, and a program that shows the entry after a failed search reads past the table unless it checks the index itself.
The AT END branch is the only place a not-found message can come from, and it is optional. A SEARCH without one and without a match does nothing at all, which is the silent path this course avoids in every program that looks up a key.
The name SEARCH takes
The verb wants the entry with the OCCURS, not the group that holds it. Naming the group is refused, with a message that points at the group and not at the entry that carries the index:
IDENTIFICATION DIVISION.
PROGRAM-ID. GROUPNAME.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 WORDS-T.
05 WORD-E PIC X(2) OCCURS 4 TIMES INDEXED BY I.
01 SEEK-F PIC X(2) VALUE "BB".
PROCEDURE DIVISION.
SET I TO 1.
SEARCH WORDS-T
AT END DISPLAY "not found"
WHEN WORD-E(I) = SEEK-F
DISPLAY "found at " I
END-SEARCH.
STOP RUN.
cobc -x -free -Wall -o groupname group.cob
./groupname
group.cob:12: error: 'WORDS-T' not indexed
10 | PROCEDURE DIVISION.
11 | SET I TO 1.
12 > SEARCH WORDS-T
13 | AT END DISPLAY "not found"
14 | WHEN WORD-E(I) = SEEK-F
group.cob:6: note: 'WORDS-T' defined here
4 | DATA DIVISION.
5 | WORKING-STORAGE SECTION.
6 > 01 WORDS-T.
7 | 05 WORD-E PIC X(2) OCCURS 4 TIMES INDEXED BY I.
8 | 01 SEEK-F PIC X(2) VALUE "BB".
The block above is a deliberate mistake and builds nothing. The fix is one word: SEARCH WORD-E. The lesson on SEARCH ALL takes the same table and the same entry, adds a sorted key and replaces the walk with a binary search.
Exercises
- Remove the second SET IDX TO 1 from the first program and run it. What does the second search report, and why?
- Move the DISPLAY ... IDX of a failed search into the AT END branch and see what it prints.
- Search a table of ten entries for a key in the last one. How many comparisons does the search make, and how would you count them?
- Add a third "BB" to the duplicate table and search three times. What has to happen between the searches?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does SEARCH do on each pass?
Answer
It tests the WHEN conditions on the entry and moves the index on by one
The verb is a loop over the entries in index order, ending at the first condition that is true.
-
Where does a SEARCH begin?
Answer
At the current value of the index
The program sets the index before the search, and the page shows what happens when it does not reset it.
-
Where is the index after a failed search?
Answer
One past the last entry, which is not a valid entry
The run printed six for a table of five, so the index is past the table.
-
Which name does SEARCH take?
Answer
The entry with OCCURS and INDEXED BY, not the group above it
Naming the group fails with the message that the group is not indexed.
-
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 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 E-F AT END DISPLAY "missing" WHEN E-F(I) = K-F DISPLAY "found " I END-SEARCH. STOP RUN.Answer
found +000000003
CC is the third entry, and the index is printed in its signed form.
-
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 3 TIMES INDEXED BY I. 01 K-F PIC X(2) VALUE "ZZ". PROCEDURE DIVISION. MOVE "AA" TO E-F(1). MOVE "BB" TO E-F(2). MOVE "CC" TO E-F(3). SET I TO 1. SEARCH E-F AT END DISPLAY "missing" WHEN E-F(I) = K-F DISPLAY "found" END-SEARCH. STOP RUN.Answer
missing
No entry matches ZZ, so the search reaches AT END.
-
What does this program print?
IDENTIFICATION DIVISION. PROGRAM-ID. Q7. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC 9(2) OCCURS 3 TIMES INDEXED BY I. 01 S-F PIC 9(3) VALUE 0. PROCEDURE DIVISION. MOVE 4 TO E-F(1). MOVE 5 TO E-F(2). MOVE 6 TO E-F(3). SET I TO 1. SEARCH E-F AT END DISPLAY "none" WHEN E-F(I) IS GREATER THAN 4 MOVE E-F(I) TO S-F END-SEARCH. DISPLAY S-F. STOP RUN.Answer
005
The first entry above four is the second, which holds five.
-
What does this program print?
IDENTIFICATION DIVISION. PROGRAM-ID. Q8. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC X(2) OCCURS 4 TIMES INDEXED BY I. 01 K-F PIC X(2) VALUE "BB". PROCEDURE DIVISION. MOVE "AA" TO E-F(1). MOVE "BB" TO E-F(2). MOVE "BB" TO E-F(3). MOVE "CC" TO E-F(4). SET I TO 1. SEARCH E-F AT END DISPLAY "none" WHEN E-F(I) = K-F DISPLAY "at " I END-SEARCH. SET I UP BY 1. SEARCH E-F AT END DISPLAY "none" WHEN E-F(I) = K-F DISPLAY "next " I END-SEARCH. STOP RUN.Answer
at +000000002 / next +000000003
The index steps past the first match, so the second search finds the next BB.
-
Why does the program set the index before every search?
Answer
SEARCH starts at the current index, so a stale one skips the entries before it
The verb uses the index as its start position, which is what the duplicate-key program controls explicitly.
-
A search finds nothing and the program prints the entry at the index anyway. What does it read?
Answer
A position past the table, which is not a valid entry
A failed search leaves the index one past the last entry, so the read is out of bounds.
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