SUBROUTINE BSRCH(KEY,LIST,N,MATCH)
C This file: http://ftp.aset.psu.edu/pub/ger/fortran/hdk/bsrch.for
C
C---------------BINARY SEARCH ROUTINE WHERE N IS GIVEN AS THE NUMBER OF
C               ITEMS, MATCH IS RETURNED AS THE SUBSCRIPT OF LIST WHERE
C               LIST(MATCH)=KEY, ELSE MATCH=0.
C            MAXIMUM NUMBER OF COMPARISONS = FLOOR(LOG2(N))+1
C            AVERAGE NUMBER OF SEARCHES =APPROX=K-1 FOR N=2**K-1 OR
C                                       OR K-2**K/N FOR SMALLER N.
C    SEE KNUTH VOL 3, ALGORITHM 6.2.1B, P. 407.
C  HDK - APRIL 1978.
      CHARACTER *(*) LIST(N),KEY
      INTEGER L,U,MATCH
C---STATEMENT NUMBERS MATCH KNUTH'S ALGORITHM.
1     L=1
      U=N
2     IF(U.LT.L) THEN
        MATCH=0
        RETURN
      ELSE
        MATCH=(L+U)/2
      END IF
C-----IF(KOMP(KEY,LIST(MATCH)) 4,7,5
3     IF(KEY.LT.LIST(MATCH)) THEN
4        U=MATCH-1
         GO TO 2
      ELSE IF(KEY.GT.LIST(MATCH)) THEN
5             L=MATCH+1
              GO TO 2
           ELSE
              RETURN
           END IF
      END