C C C B S E R C H C C BINARY SEARCH ROUTINE C C THIS ROUTINE USES A BINARY SEARCHTECHNIQUE TO LOCATE AN ITEM IN A C SORTED LIST. THE ROUTINE ASSUMES THAT EACH ENTRY IN THE TABLE , AND C THE ITEM BEING SEARCHED FOR , IS LEN BYTES LONG. THE TABLE MUST BE IN C ASCENDING ORDER. THE ALGORITHM FOR THE SEARCH IS AS FOLLOWS: C C A1: THE LOWER BOUND OF THE SEARCH IS SET TO 1 (BEGINNING OF THE C TABLE )AND THE UPPER BOUND IS SET TO THE LAST ITEM IN THE C TABLE ( SIZE ) C A2: THE MIDDLE ITEM IN THIS RANGE (/2) C IS COMPARED TO THE DESIRED ITEM. C A3: IF A MATCH IS FOUND GO TO STEP A9 C A4: IF THE ITEM BEING SEARCHED FOR IS LESS THAN THE MIDDLE ITEM C THEN SET THE UPPER LIMIT TO THE MIDDLE ITEM INDEX -1 AND GO C TO STEP A6 C A5: IF THE ITEMBEING SEARCHEDFOR IS GREATER THAN THE MIDDLE C ITEM THE SET THE LOWER LIMIT TO THE MIDDLE ITEM INDEX + 1 . C A6: IF THE LOWER LIMIT IS EQUAL TO THE UPPER LIMIT THEN COMPARE C THE ITEM TO THIS TABLE ENTRY AND IF EQUAL THE GO TO STEP A9 C ELSE GO TO A10 . C A7: IF THE LOWER LIMIT IS GREATERTHAN THE UPPER LIMIT THEN GO C TO STEP A10 . C A8: SINCE LOWER LIMIT IS LESS THAN UPPER LIMIT GO TO STEP A2 TO C TRY NEXT COMPARISON. C A9: RETURN INDEX TO ITEM IN TABLE (THE CALCULATED MIDDLE INDEX) C A10: RETURN AN INDEX OF -1 TO INDICATE THAT ITEM WAS NOT FOUND. C C C THE CALLING SEQUENCE IS: C C CALL BSERCH ( TABLE , SIZE , ITEM , LEN , INDEX ) C C WHERE: C TABLE- INTEGER ARRAY CONTAINING THE DATA ITEMS TO BE SEARCHED. C THE TABLE MUST BE SORTED IN ASCENDING ORDER. C SIZE- INTEGER VARIABLE CONTAINING A COUNT OF THE NUMBER OF C ENTRIES IN TABLE. C ITEM- INTEGER ARRAY CONTAINING THE ITEM TO BE SEARCHED C FOR IN TABLE. C LEN- LENGTH OF THE ITEM IN BYTES. C INDEX- INTEGER VARIABLE WHICH , UPON RETURN , WILL CONTAIN AN C INDEX TO THE TABLE LOCATION WHERE THE ITEM WAS FOUND.IF C THE ITEM WAS NOT FOUND THEN INDEX IS SET TO -1 C C NOTE THAT THE TABLE ENTRIES AND THE ITEM SHOULD BE LEFT JUSTIFIED C AND BLANK FILLED C C SUBROUTINE BSERCH ( TABLE , SIZE , ITEM , LEN , INDEX ) INTEGER SIZE , INDEX, LOWLIM , HIGLIM , COMPAR, LEN BYTE ITEM(LEN) , TABLE(LEN,SIZE) D WRITE (5,1) ITEM D 1 FORMAT (' BSERCH START, LOOKING FOR ',A1) LOWLIM = 1 !LOWER LIMIT OF SEARCH RANGE HIGLIM = SIZE !UPPER LIMIT OF SEARCH RANGE 10 CONTINUE COMPAR = ( LOWLIM + HIGLIM ) / 2 !MIDDLE ITEM FOR COMPARE D WRITE (5,3) COMPAR,(TABLE(I,COMPAR),I=1,LEN) D 3 FORMAT (' BSERCH COMPARING ITEM TO INDEX ',I4,2X,A1) DO 20 K = 1,LEN !COMPARE MIDDLE AND GIVEN ITEM IF ( ITEM(K)-TABLE(K,COMPAR) ) 30 , 20 , 40 20 CONTINUE INDEX = COMPAR !GIVEN ITEM FOUND GO TO 150 30 CONTINUE HIGLIM = COMPAR - 1 !GIVEN ITEM < MIDDLE ITEM GO TO 50 40 CONTINUE LOWLIM = COMPAR + 1 !GIVEN ITEM > MIDDLE ITEM 50 CONTINUE IF ( LOWLIM - HIGLIM ) 10 , 60 , 100 60 CONTINUE !COMPARE LAST MIDDLE AND GIVEN ITEMS DO 70 K = 1,LEN IF ( ITEM(K) .NE. TABLE(K,HIGLIM) ) GO TO 100 70 CONTINUE INDEX = HIGLIM GO TO 150 100 CONTINUE INDEX = -1 !ITEM NOT FOUND 150 CONTINUE D WRITE (5,2) INDEX D 2 FORMAT (' BSERCH END, INDEX = ',I4) RETURN END