Searching and the Search Verb

We have seen how to code a our own table search, now we will look at an alternative, the SEARCH verb. The SEARCH verb automates the search process and is useful in a large percentage of the times when you need to do a search. Before we actually discuss the SEARCH verb, you should review and understand the logic of a search.

There are two kinds of searches: the LINEAR SEARCH and the BINARY SEARCH. Both can be coded by the programmer using traditional code or coded by the programmer using the SEARCH verb.

The search that is coded by the programmer using traditional code uses an OCCURS to define the reoccurrence of the elements in the table and the subscript to control stepping through the table one element at a time using the looping. Let's take a closer look at a subscript. A subscript is essentially a pointer that points to one of the elements in the table. The subscript is a traditional field under the control of the programmer. The subscript is usually initialized with a MOVE statement and incremented with an ADD statement (or a SUBTRACT statement if the subscript was being decreased). The subscript is defined by the programmer.

In contrast to the subscript, the SEARCH verb uses an index which is defined by name with the table. The actual setup of the index is done through COBOL. The index is limited in use. It must be used with the table that defined it and it must be controlled using either the PERFORM statement with the varying clause or the SET verb. Essentially a programmer has far more control over the manipulation of a subscript than an index. Because the index is used with the SEARCH verb, the restrictions are defined to maximize it effective use in that context.

Linear Search:

The search that we have looked at is a linear search. A linear search checks the field we need to match against each element in the table to see if they match. Traditionally the search starts with the first element in the table and ends when either a match is found or we have checked every record in the table. It should be noted that if the elements in the table are in order, an early exit can be coded. Looking at the soup example, the item numbers are in order. If we are looking for a match to 18, we don't have to search the whole table, we can stop looking when the item in the table is greater that the number we are looking for, 18. In other words, when the search compares 18 to the 24 in the table, we can declare the search over since we have passed the point where the match would have been. This example of the search has an early exit which is done by simply modifying the PERFORM UNTIL. The change has been highlighted. Take a minute to review the traditional search below and then we will move on to the search verb.

01  TABLE-COMBINED.
    05  FILLER    PIC X(17)  VALUE "03SEAFOOD CHOWDER".
    05  FILLER    PIC X(17)  VALUE "12CORN CHOWDER   ".
    05  FILLER    PIC X(17)  VALUE "15CLAM CHOWDER   ".
    05  FILLER    PIC X(17)  VALUE "17TOMATO SOUP    ".
    05  FILLER    PIC X(17)  VALUE "24CHICKEN SOUP   ".
    05  FILLER    PIC X(17)  VALUE "25VEGETABLE SOUP ".
    05  FILLER    PIC X(17)  VALUE "27ONION SOUP     ".
    05  FILLER    PIC X(17)  VALUE "28GREEN PEA SOUP ".
    05  FILLER    PIC X(17)  VALUE "45WONTON SOUP    ".
01  RDF-TABLE-COMBINED REDEFINES TABLE-COMBINED.
    05  ENTRIES   OCCURS 9 TIMES.
        10  ITEM-NUMBER-TBL      PIC 99.
        10  ITEM-NAME-TBL        PIC X(15).

B-200-LOOP.
    ...
    ... processing not related to search ...
    ...
    MOVE 1 TO ITEM-SUB.
    MOVE "NO " TO MATCH-IND.
    PERFORM B-300-SEARCH
        UNTIL ITEM-SUB  9 OR 
              ITEM-NUMBER-TBL (ITEM-SUB)  ITEM-NUMBER-IN OR 
              MATCH-IND = "YES".
    IF MATCH-IND = "YES"
        MOVE ITEM-NAME-TBL (ITEM-SUB) TO ITEM-NAME-PR
    ELSE
        MOVE ERROR-MSG-TBL TO ITEM-NAME-PR.
    ...
    ... processing not related to search...
    ...
B-300-SEARCH.
    IF ITEM-NUMBER-IN = ITEM-NUMBER-TBL (ITEM-SUB)
        MOVE "YES" TO MATCH-IND
    ELSE
        ADD 1 TO ITEM-SUB.


Now we will do the same search using the SEARCH verb. First, we need to define the table. The difference is that in defining the table, we also establish the index.

01  TABLE-COMBINED.
    05  FILLER    PIC X(17)  VALUE "03SEAFOOD CHOWDER".
    05  FILLER    PIC X(17)  VALUE "12CORN CHOWDER   ".
    05  FILLER    PIC X(17)  VALUE "15CLAM CHOWDER   ".
    05  FILLER    PIC X(17)  VALUE "17TOMATO SOUP    ".
    05  FILLER    PIC X(17)  VALUE "24CHICKEN SOUP   ".
    05  FILLER    PIC X(17)  VALUE "25VEGETABLE SOUP ".
    05  FILLER    PIC X(17)  VALUE "27ONION SOUP     ".
    05  FILLER    PIC X(17)  VALUE "28GREEN PEA SOUP ".
    05  FILLER    PIC X(17)  VALUE "45WONTON SOUP    ".
01  RDF-TABLE-COMBINED REDEFINES TABLE-COMBINED.
    05  ENTRIES   OCCURS 9 TIMES
                  INDEXED BY ITEM-INDX.
        10  ITEM-NUMBER-TBL      PIC 99.
        10  ITEM-NAME-TBL        PIC X(15).

The linear SEARCH verb uses the SET statement to establish the index prior to the search. The SEARCH verb is than used to execute the linear search.

The format of the SET statement is:

SET {index-name-1} TO {index-name-2}
    {data-name-1 } TO {data-name-2 }
                      {integer     }

There is also a special format for adding to or decreasing the index:

SET {index-name} {UP BY  }   {data-name}
                 {DOWN BY}   {integer  }

The format of the linear SEARCH verb is:

SEARCH {table-name} [VARYING {index-name}]
             [AT END processing-code-1]
     {WHEN condition {processing-code-2}
                     {NEXT SENTENCE    }
[END-SEARCH]

Using the SEARCH verb, the search for a match in the soup table, would be:

B-200-LOOP.
    ...
    ... processing not related to search ...
    ...
    SET ITEM-INDX TO 1.
    SEARCH ENTRIES
        AT END
            MOVE ERROR-MSG-TBL TO ITEM-NAME-PR
        WHEN ITEM-NUMBER-TBL (ITEM-INDX) = ITEM-NUMBER-IN
            MOVE ITEM-NAME-TBL (ITEM-INDX) TO ITEM-NAME-PR
    ...
    ... processing not related to search...
    ...

Things to take note of:



Notice that in the search you code yourself and the SEARCH verb there are some similarities.

Binary search:

A binary search is a very efficient search when you are dealing with a large table. Note that a binary search will only work if the table is in order by the element you are searching. A binary search looks at the first item in the table. If a match is found, the search is done. If a match is not found, it checks to see if the item you are trying to match is larger or smaller than the middle element. If it is larger, than we know that we only have to look at the half of the table past the middle. If it is smaller, than we know that we only have to look at the half of the table before the middle. Based on this decision, we have eliminate half the table from the search. We next look at the middle item in the half that is left and compare it to the element. This will either find a match or eliminate another quarter of the table. Note that in establishing what the middle is if the number of elements is even, the programmer of a binary search can choose to round or truncate. This process continue until either a match is found or it is clear that the element is not in the table.

Looking at the item numbers in our soup example, the binary search would proceed in this manner to find a match for the number 27:

03

12

15

17

24

25

27

28

45

 

 

 

 

first search since 27 is
the first half is gone

 

 

 

 

 

 

 

 

 

 

second search and match
found

 

 


The programmer can code their own binary search or they can use the SEARCH verb in its binary search format of SEARCH ALL. When coding the binary search, the index is totally controlled by the search verb so no SET statement is used. The binary search with the SEARCH ALL that would be used with our soup example is:

B-200-LOOP.
    ...
    ... processing not related to search ...
    ...
    SEARCH ALL ENTRIES
        AT END
            MOVE ERROR-MSG-TBL TO ITEM-NAME-PR
        WHEN ITEM-NUMBER-TBL (ITEM-INDX) = ITEM-NUMBER-IN
            MOVE ITEM-NAME-TBL (ITEM-INDX) TO ITEM-NAME-PR
    ...
    ... processing not related to search...
    ...	

Note that in the linear search the WHEN condition does not have to be an equals condition, however in the binary search the WHEN condition is required to be an equals condition. Based on the logic of the binary search, only a comparison for an equal match makes any sense.