C #BNSCHA V1A 18-MAY-73. C LAST UPDATE: C SUBROUTINE BNSCHA ( MATCH, ILO, IHI, IPT) C C *PURPOSE. C TO PERFORM A BINARY SEARCH IN AN INTEGER RANGE "ILO" C TO "IHI" FINDING THE LARGEST VALUE SUCH THAT MATCH(IPT)<=0 C AND MATCH(IPT+1)>0. WHERE "MATCH" IS A USER SUPPLIED INTEGER C FUNCTION WHICH IS INCREASING WITH "IPT". C FOR EXAMPLE "MATCH" COULD BE THE DIFFERENCE BETWEEN A C GIVEN VALUE AND THE "IPT"TH ENTRY IN AN ORDERED TABLE. C C *PARAMETERS: C C MATCH - THE EXTERNAL NAME OF A USER SUPPLIED FUNCTION WHICH C DIRECTS THE SEARCH AS STATED ABOVE. C ILO - THE LOWER BOUND OF THE SEARCH. C IHI - THE UPPER BOUND OF THE SEARCH. C IPT - THE RETURNED RESULT OF THE SEARCH. THE EXTREME VALUES C ARE ILO-1 INDICATING AN UNDERFLOW (I.E. ALL MATCH C VALUES WERE >0 ) AND IHI INDICATING AN OVERFLOW C (I.E. ALL MATCH VALUES WERE <0 ). C C INPUT PARAMETERS: C MATCH, ILO, IHI C OUTPUT PARAMETERS: C IPT C C *METHOD. C AFTER CHECKING FOR THE OVERFLOW AND UNDERFLOW CONDITIONS C A STANDARD BINARY SEARCH IS PERFORMED. NOTE THAT IF NO EXACT C MATCH IS FOUND THE RETURNED VALUE POINTS TO THE MATCH VALUE C JUST BELOW THE ZERO. C C *ACCURACY. C C *RESTRICTIONS. C C *ERROR CONDITIONS. C SEE ABOVE FOR OVERFLOW AND UNDERFLOW INDICATIONS. C C *NON STANDARD ROUTINES CALLED. C MATCH (USERS). C C *TYPICAL TIMES. C ROUGHLY LOG(IHI-ILO) TO BASE 2 MATCH VALUES MAY BE C REQUIRED. C C *ORIGIN. M.R.MANNING C C *COMMENTS. C C #END. C C #START. IPT= ILO IF (MATCH(ILO) ) 10, 100, 90 10 IF (MATCH(IHI) ) 80, 80, 20 20 ITOP= IHI C NOW HAVE ENSURED THAT IPT IS IN RANGE START SEARCH 30 IF (ITOP - IPT .LE. 1) GO TO 100 MID= (ITOP + IPT)/2 IF (MATCH(MID) ) 60, 50, 70 C WATCH IT - EXACT MATCH! 50 IPT= MID GO TO 100 C TOO LOW! 60 IPT= MID GO TO 30 C TOO HIGH! 70 ITOP= MID GO TO 30 C C EXITS: C C OVERFLOW 80 IPT= IHI RETURN C UNDERFLOW 90 IPT= ILO - 1 C NORMAL 100 RETURN C END