Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 38 ยท Tables and Arrays

Indexes and SEARCH

Learn COBOL table lookups with INDEXED BY, SET, SEARCH and SEARCH ALL - linear versus binary search, key ordering rules, AT END handling and the difference between an index and a subscript.

Looking something up in a table is one of the most common jobs in business code: find the tax rate for a state, the price for a product code, the name for a department number. You could write the loop yourself with a subscript, but COBOL has two statements built for the job, SEARCH and SEARCH ALL, and they work with a special kind of subscript called an index.

This lesson explains what an index is, how SET changes it, how a linear SEARCH walks the table, and how SEARCH ALL performs a binary search on a sorted table.

Index versus subscript

An ordinary subscript is a numeric data item, for example I PIC 99. To locate an entry the program computes (I - 1) x entry-length on every access. An index is created with INDEXED BY on the OCCURS clause. The compiler stores in it the byte displacement from the table start, so no multiplication is needed:

COBOL
       01  STATE-TABLE.
           05  STATE-ENTRY OCCURS 5 TIMES
                   ASCENDING KEY IS STATE-CODE
                   INDEXED BY ST-IX.
               10  STATE-CODE  PIC XX.
               10  STATE-RATE  PIC V999.

ST-IX needs no separate PIC clause; it is declared by the INDEXED BY phrase. Because an index holds a displacement, you cannot MOVE a number into it or DISPLAY it directly. You use:

  • SET ST-IX TO 1 to point at entry 1.
  • SET ST-IX UP BY 1 or DOWN BY 1 to move.
  • SET WS-NUMBER TO ST-IX to read the entry number back into a normal numeric item.

You may still use a regular subscript on the same table. An index and an ordinary subscript can be mixed in different statements, but you cannot mix them inside one subscript list in standard COBOL, so use ST-IX consistently with this table.

SEARCH starts at the entry the index currently points to and tests each entry in turn until a WHEN condition is true or the table ends. You must set the index yourself first:

COBOL
           SET ST-IX TO 1
           SEARCH STATE-ENTRY
               AT END
                   DISPLAY "Unknown state: " IN-STATE
               WHEN STATE-CODE (ST-IX) = IN-STATE
                   COMPUTE TAX = AMOUNT * STATE-RATE (ST-IX)
           END-SEARCH

How it behaves:

  1. It checks the WHEN conditions in order for the current entry.
  2. If none is true it moves the index up by one and repeats.
  3. If the index passes the last entry, the AT END branch runs. If there is no AT END and nothing matched, execution simply continues after END-SEARCH with the index beyond the table, which is a classic bug. Always code AT END.

The table does not need to be sorted, and you may have several WHEN clauses. The cost grows with the table length, which is fine for 50 entries and slow for 50,000.

Forgetting SET ST-IX TO 1 is the most common error: the search starts wherever the index was left by the previous lookup, so it may miss entries that lie before it.

SEARCH ALL halves the range on every step. It requires three things:

  • The table has ASCENDING KEY (or DESCENDING KEY) and an INDEXED BY clause.
  • The entries are already in that key order. COBOL does not sort them for you, and on unordered data the result is undefined: you may get "not found" for a code that is present.
  • The WHEN tests the key with = (possibly joined by AND with other key equalities). Other operators are not allowed.
COBOL
           SEARCH ALL STATE-ENTRY
               AT END
                   DISPLAY "Unknown state: " IN-STATE
               WHEN STATE-CODE (ST-IX) = IN-STATE
                   COMPUTE TAX = AMOUNT * STATE-RATE (ST-IX)
           END-SEARCH

No SET is needed before SEARCH ALL; the runtime manages the index itself. For a table of 1,024 entries a linear search averages about 512 comparisons, a binary search about 10.

flowchart TD
    S["Table of 8 sorted keys<br/>looking for 'NY'"] --> M1["Compare middle entry (4)"]
    M1 -->|"key too small"| R["Search upper half (5-8)"]
    M1 -->|"key too large"| L["Search lower half (1-3)"]
    R --> M2["Compare middle of half"]
    M2 --> F["Found, or AT END when range is empty"]

Each comparison discards half of the remaining entries.

Loading a sorted table

In practice rate tables are loaded from a file at the start of the run. Loading in key order is your job; the sort step or the file itself should guarantee it. A cheap safety check in the load loop is to compare each key with the previous one and stop with an error message if the order is broken. See sorting and merging for how to put data in order.

Walking with PERFORM and SET

When you need your own loop with an index, combine SET and PERFORM:

COBOL
           PERFORM VARYING ST-IX FROM 1 BY 1 UNTIL ST-IX > 5
               DISPLAY STATE-CODE (ST-IX) " " STATE-RATE (ST-IX)
           END-PERFORM

PERFORM VARYING accepts an index as the varying item. Inside the loop you can use ST-IX as the subscript.

Seeing the algorithms

The following two stand-ins are labelled as Python models of the two statements. They show the control flow, including the AT END case, with one-based positions like COBOL.

Python Stand-in: SEARCH (linear) with AT END

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Stand-in: SEARCH ALL (binary) counts its comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second block prints the sorted keys and the position and number of steps for each lookup; none needs more than four comparisons for eight entries (NY is found in one, AK in three).

Choosing between them

Situation Use
Small table, unordered or needs >, < or ranges SEARCH
Large table sorted on a key, exact match SEARCH ALL
Table changes often and cannot be kept sorted SEARCH or rebuild the order
Range lookup such as tax brackets SEARCH with WHEN INCOME <= BRACKET-LIMIT (IX)

Put the most frequent keys first in a linear table. The average cost drops without any other change.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What must you do before a linear SEARCH?

    SEARCH starts at the index's current position, so SET ST-IX TO 1 is needed to search from the beginning.
  2. 2. Which requirement applies to SEARCH ALL?

    Binary search depends on order, so the table needs an ASCENDING or DESCENDING KEY, an index, and the data must really be sorted.
  3. 3. What happens in a SEARCH with no AT END when nothing matches?

    Silent fall-through is allowed, which is why you should always code AT END.
  4. 4. How do you copy an index value into an ordinary numeric field?

    An index stores a displacement, so only SET converts it to and from an entry number.

Summary

  • INDEXED BY creates an index, a displacement-based subscript changed with SET.
  • SEARCH is a linear scan from the current index; set the index first and always code AT END.
  • SEARCH ALL is a binary search that needs ASCENDING/DESCENDING KEY, sorted data and equality tests.
  • Choose by table size, ordering and the kind of comparison you need.

Next: Multi-dimensional tables and variable length