Easytrieve binary search algorithm example
Article ID: 10421
Updated On:
Products
Issue/Introduction
One of the advantages of the binary search algorithm in opposite to the linear search algorithm is a huge possibility of improvement and to make your program much more efficient.
Please note:
In order to use the binary search algorithm, the records must be sorted.
Environment
Easytrieve Report Generator, release 11.6
Resolution
In order to compare both algorithms, the search loops are being called 2000 times in the following sample.
The first line is showing the result when using the linear search algorithm, and the 2nd line is showing the result when using the binary search algorithm - compare TOT-CPU please:
STEPNAME STEP PGM= CCODE EST-COST EXCPS ELAPSED TOT-CPU
EZTPGM 1 EB6L2KP 0000 $5.89 958 00:00:02.27 00:00:01.34
EZTPGM 1 EB6B2KP 0000 $4.79 958 00:00:00.47 00:00:00.03
...
Here are the source samples - first the linear search:
...
PARM LINK(EB6L2KP R)
*----------------------------------------------------------------------*
* DEFINITIONS *
*----------------------------------------------------------------------*
FILE FILE1
FILE-CODE 1 8 N
FILE-DESC * 40 A
*
TABLE1-ELEMENTS W 48 A OCCURS 30000
TABLE-CODE TABLE1-ELEMENTS 8 N
TABLE-DESC TABLE1-ELEMENTS +8 40 A
*
DEFINE SRCH-VALUE W 08 N VALUE 15001
DEFINE CNTR1 W 08 N VALUE 1
DEFINE CNTR2 W 08 N VALUE 1
*
*----------------------------------------------------------------------*
* WRITE (SORTED) RECORDS FROM FILE1 TO WORK TABLE *
*----------------------------------------------------------------------*
JOB INPUT FILE1
TABLE-CODE(CNTR1) = FILE-CODE
TABLE-DESC(CNTR1) = FILE-DESC
CNTR1 = CNTR1 + 1
*----------------------------------------------------------------------*
* LINEAR SEARCH IN WORK TABLE *
*----------------------------------------------------------------------*
JOB INPUT NULL
CNTR1 = 0
DO UNTIL CNTR1 = 2000
DO WHILE CNTR2 LT 30001
IF TABLE-CODE(CNTR2) = SRCH-VALUE
DISPLAY 'SEARCH VALUE HAS BEEN LOCATED: '
DISPLAY TABLE-DESC(CNTR2)
CNTR2 = 30001
END-IF
CNTR2 = CNTR2 + 1
END-DO
CNTR2 = 1
CNTR1 = CNTR1 + 1
END-DO
STOP
...
And the binary search sample:
...
PARM LINK(EB6B2KP R)
*----------------------------------------------------------------------*
* DEFINITIONS *
*----------------------------------------------------------------------*
FILE FILE1
FILE-CODE 1 8 N
FILE-DESC * 40 A
*
TABLE1-ELEMENTS W 48 A OCCURS 30000
TABLE-CODE TABLE1-ELEMENTS 8 N
TABLE-DESC TABLE1-ELEMENTS +8 40 A
*
DEFINE SRCH-VALUE W 08 N VALUE 15001
DEFINE CNTR1 W 08 N VALUE 1
DEFINE CNTR2 W 08 N VALUE 1
DEFINE FOUND W 01 N VALUE 0
DEFINE TOP W 08 N VALUE 30000
DEFINE BOT W 08 N VALUE 1
DEFINE MID W 08 N VALUE 1
*
*----------------------------------------------------------------------*
* WRITE (SORTED) RECORDS FROM FILE1 TO WORK TABLE *
*----------------------------------------------------------------------*
JOB INPUT FILE1
TABLE-CODE(CNTR1) = FILE-CODE
TABLE-DESC(CNTR1) = FILE-DESC
CNTR1 = CNTR1 + 1
*----------------------------------------------------------------------*
* BINARY SEARCH IN WORK TABLE *
*----------------------------------------------------------------------*
JOB INPUT NULL
CNTR1 = 0
DO UNTIL CNTR1 = 2000
DO WHILE FOUND = 0 AND TOP >= BOT
MID = (TOP + BOT) / 2
IF SRCH-VALUE = TABLE-CODE(MID)
DISPLAY 'SEARCH VALUE HAS BEEN LOCATED: '
DISPLAY TABLE-DESC(MID)
FOUND = 1
ELSE
IF SRCH-VALUE < TABLE-CODE(MID)
TOP = MID - 1
ELSE
BOT = MID + 1
END-IF
END-IF
END-DO
FOUND = 0
CNTR2 = 1
CNTR1 = CNTR1 + 1
END-DO
STOP
...
FILE1:
****** ********************************* Top of Data **********************************
000001 00000001DESCRIPTION OF LINE 00000001
000002 00000002DESCRIPTION OF LINE 00000002
000003 00000003DESCRIPTION OF LINE 00000003
- - - - - - - - - - - - - - - - - - - - 29994 Line(s) not Displayed
029998 00029998DESCRIPTION OF LINE 00029998
029999 00029999DESCRIPTION OF LINE 00029999
030000 00030000DESCRIPTION OF LINE 00030000
****** ******************************** Bottom of Data ********************************
Additional Information
from https://docops.ca.com/ca-easytrieve/11-6/en/programming/code-programs/code-efficient-programs :
...
Table Processing
Avoid using very large tables, because they take more time to search and require more storage than small tables.
Note: Easytrieve® automatically converts a SEARCH of an INDEXED table file into a keyed read when the ARG field is also the file's key. This results in much faster access and reduced storage requirements.
...
Feedback
