Chicago-Soft
ATTN: TSO Times
One Maple Street
Hanover, NH 03755
(603) 643-4002
information
@tsotimes.com

Quick Tip - Binary Search REXX Exec

by Henry L. Farineau

The BINSRCH REXX exec contains simple binary search logic which will quickly locate a record in a sequential file based on a unique sorted sequence key. The maximum number of iterations in the "do forever" loop for any one search is equal to the number of times the maximum number of records is divisable by 2. So, for a file that has 8000 records, the maximum number of iterations is 13 since 2**13 = 8192.

In this example the file, TEST.FILE, contains records that are sorted by the first 4 positions of the record. Obviously, this code may be incorporated into more complex REXX execs to enable a keyed search of a sorted sequential file without having to process through the file one record at a time.

If you want to search the data from a KSDS VSAM file, use IDCAMS REPRO to produce a sequential copy of the file, then use this code to perform your search.

/* REXX */	
ARG SRCHARG	/* Set search argument	*/

/*  File requirement: Sequential file where the search argument is 
unique within the file, and the file is sorted in ascending sequence by that field.	*/	
	
"ALLOC F(DD1) DA('TEST.FILE') SHR REUSE"                        /* Allocate sequential file */
"EXECIO * DISKR DD1 (STEM DD1. FINIS"                       	/* Read records into stem variables  */
	
DO UNTIL SRCHARG = "" | SRCHARG = EXIT	
	MIN = 0	               					/* Initialize lowest rec #  */
	MAX = DD1.0 + 1	     					/* Initialize highest rec #	*/
	MIDPOINT = MAX % 2   					/* Calculate midpoint of file  */

	DO UNTIL FILEARG = SRCHARG | MIDPOINT = MIN		/* Iterative loop	*/

	FILEARG = SUBSTR(DD1.MIDPOINT,1,4)			/* Set variable for search compare	*/
	SELECT
	WHEN SRCHARG < FILEARG THEN MAX = MIDPOINT		/* SRCHARG in lower half...reset MAX */
	WHEN SRCHARG > FILEARG THEN MIN = MIDPOINT		/* SRCHARG in upper half...reset MIN */	
	OTHERWISE NOP
	END  
	MIDPOINT = MIN + ((MAX - MIN) % 2)			/* Re-calculate midpoint */
	END 
	
	IF SRCHARG = FILEARG THEN SAY SRCHARG "FOUND"		/* Indicate a hit	*/
	ELSE SAY SRCHARG "NOT FOUND"     			/* Indicate a miss */

	SAY "Enter a new search argument"                       /* Prompt for a new search argument */              
        PULL SRCHARG   						/* Retrieve the new search argument */
END

EXIT

Henry L. Farineau, Allmerica Financial, Worcester, Massachusetts

home · current articles · archives · forums ·
· subscribe · about us · contact us · links