BinSearch.F90 Source File

module BinSearch_int

    use constants
    use util_mod_comparisons, only: operator(.arrgt.), operator(.arrlt.)
    implicit none
    interface BinarySearch
        module procedure BinarySearch_int
    end interface

contains
!A binary search
! List is an ordered list of length Length
! MinInd and MaxInd are the bounds within this list of the search
! We search for Value in this list.
!  If it is found, its location is placed in FoundIndex and tSuccess is set to .TRUE.
!  If not, then the index of the largest item less than Value is placed in FoundIndex, and tSuccess is set to .FALSE.

    SUBROUTINE BinarySearch_int(Value,List,MinInd,MaxInd,FoundIndex,tSuccess)
        INTEGER :: MinInd,MaxInd,FoundIndex
        integer(kind=int32), intent(in) :: Value
        integer(kind=int32), intent(in) :: List(:)
        INTEGER :: i,j,N
        LOGICAL :: CompLT,CompGT
        LOGICAL :: tSuccess

        i=MinInd
        j=MaxInd
        tSuccess=.false.
        do while(j-i.gt.0)  !End when the upper and lower bound are the same.
            N=(i+j)/2       !Find the midpoint of the two indices

            CompLT=List(N) < Value
            CompGT=List(N) > Value

            IF(.not.(CompLT.or.CompGT)) THEN ! If it's neither larger or smaller, it's there.
!Praise the Lord, we've found it!
                tSuccess=.true.
                FoundIndex=N
                RETURN
            ELSEIF(CompLT) THEN
               if(i.eq.N) THEN
                  !This happens when j=i+1.  See if j==Value
                  CompLT=List(j) < Value
                  CompGT=List(j) > Value
                  if(.not.CompGT) then
                     tSuccess=.not.CompLT !If j's not > or <, it must be ==
                     i=j                  !j's not >, so we move up to it.
                  endif
                  FoundIndex=i
                  RETURN
               ENDIF
               !move the lower bound up
               i=N
            ELSE !it must be larger!
               !move the upper bound down
               j=N
            ENDIF
         enddo

!Here i=j=N, but .not.CompLT.  We signal failure and set FoundIndex to 1 before Min.
         FoundIndex=i-1
         RETURN
    END SUBROUTINE

end module



module BinSearch_int64

    use constants
    use util_mod_comparisons, only: operator(.arrgt.), operator(.arrlt.)
    implicit none
    interface BinarySearch
        module procedure BinarySearch_int64
    end interface

contains
!A binary search
! List is an ordered list of length Length
! MinInd and MaxInd are the bounds within this list of the search
! We search for Value in this list.
!  If it is found, its location is placed in FoundIndex and tSuccess is set to .TRUE.
!  If not, then the index of the largest item less than Value is placed in FoundIndex, and tSuccess is set to .FALSE.

    SUBROUTINE BinarySearch_int64(Value,List,MinInd,MaxInd,FoundIndex,tSuccess)
        INTEGER :: MinInd,MaxInd,FoundIndex
        integer(kind=int64), intent(in) :: Value
        integer(kind=int64), intent(in) :: List(:)
        INTEGER :: i,j,N
        LOGICAL :: CompLT,CompGT
        LOGICAL :: tSuccess

        i=MinInd
        j=MaxInd
        tSuccess=.false.
        do while(j-i.gt.0)  !End when the upper and lower bound are the same.
            N=(i+j)/2       !Find the midpoint of the two indices

            CompLT=List(N) < Value
            CompGT=List(N) > Value

            IF(.not.(CompLT.or.CompGT)) THEN ! If it's neither larger or smaller, it's there.
!Praise the Lord, we've found it!
                tSuccess=.true.
                FoundIndex=N
                RETURN
            ELSEIF(CompLT) THEN
               if(i.eq.N) THEN
                  !This happens when j=i+1.  See if j==Value
                  CompLT=List(j) < Value
                  CompGT=List(j) > Value
                  if(.not.CompGT) then
                     tSuccess=.not.CompLT !If j's not > or <, it must be ==
                     i=j                  !j's not >, so we move up to it.
                  endif
                  FoundIndex=i
                  RETURN
               ENDIF
               !move the lower bound up
               i=N
            ELSE !it must be larger!
               !move the upper bound down
               j=N
            ENDIF
         enddo

!Here i=j=N, but .not.CompLT.  We signal failure and set FoundIndex to 1 before Min.
         FoundIndex=i-1
         RETURN
    END SUBROUTINE

end module



module BinSearch_double

    use constants
    use util_mod_comparisons, only: operator(.arrgt.), operator(.arrlt.)
    implicit none
    interface BinarySearch
        module procedure BinarySearch_double
    end interface

contains
!A binary search
! List is an ordered list of length Length
! MinInd and MaxInd are the bounds within this list of the search
! We search for Value in this list.
!  If it is found, its location is placed in FoundIndex and tSuccess is set to .TRUE.
!  If not, then the index of the largest item less than Value is placed in FoundIndex, and tSuccess is set to .FALSE.

    SUBROUTINE BinarySearch_double(Value,List,MinInd,MaxInd,FoundIndex,tSuccess)
        INTEGER :: MinInd,MaxInd,FoundIndex
        real(dp), intent(in) :: Value
        real(dp), intent(in) :: List(:)
        INTEGER :: i,j,N
        LOGICAL :: CompLT,CompGT
        LOGICAL :: tSuccess

        i=MinInd
        j=MaxInd
        tSuccess=.false.
        do while(j-i.gt.0)  !End when the upper and lower bound are the same.
            N=(i+j)/2       !Find the midpoint of the two indices

            CompLT=List(N) < Value
            CompGT=List(N) > Value

            IF(.not.(CompLT.or.CompGT)) THEN ! If it's neither larger or smaller, it's there.
!Praise the Lord, we've found it!
                tSuccess=.true.
                FoundIndex=N
                RETURN
            ELSEIF(CompLT) THEN
               if(i.eq.N) THEN
                  !This happens when j=i+1.  See if j==Value
                  CompLT=List(j) < Value
                  CompGT=List(j) > Value
                  if(.not.CompGT) then
                     tSuccess=.not.CompLT !If j's not > or <, it must be ==
                     i=j                  !j's not >, so we move up to it.
                  endif
                  FoundIndex=i
                  RETURN
               ENDIF
               !move the lower bound up
               i=N
            ELSE !it must be larger!
               !move the upper bound down
               j=N
            ENDIF
         enddo

!Here i=j=N, but .not.CompLT.  We signal failure and set FoundIndex to 1 before Min.
         FoundIndex=i-1
         RETURN
    END SUBROUTINE

end module



module BinSearch_int_arr

    use constants
    use util_mod_comparisons, only: operator(.arrgt.), operator(.arrlt.)
    implicit none
    interface BinarySearch
        module procedure BinarySearch_int_arr
    end interface

contains
!A binary search
! List is an ordered list of length Length
! MinInd and MaxInd are the bounds within this list of the search
! We search for Value in this list.
!  If it is found, its location is placed in FoundIndex and tSuccess is set to .TRUE.
!  If not, then the index of the largest item less than Value is placed in FoundIndex, and tSuccess is set to .FALSE.

    SUBROUTINE BinarySearch_int_arr(Value,List,MinInd,MaxInd,FoundIndex,tSuccess)
        INTEGER :: MinInd,MaxInd,FoundIndex
        integer(kind=int32), intent(in) :: Value(:)
        integer(kind=int32), intent(in) :: List(:,:)
        INTEGER :: i,j,N
        LOGICAL :: CompLT,CompGT
        LOGICAL :: tSuccess

        i=MinInd
        j=MaxInd
        tSuccess=.false.
        do while(j-i.gt.0)  !End when the upper and lower bound are the same.
            N=(i+j)/2       !Find the midpoint of the two indices

            CompLT=List(:,N) .arrlt. Value(:)
            CompGT=List(:,N) .arrgt. Value(:)

            IF(.not.(CompLT.or.CompGT)) THEN ! If it's neither larger or smaller, it's there.
!Praise the Lord, we've found it!
                tSuccess=.true.
                FoundIndex=N
                RETURN
            ELSEIF(CompLT) THEN
               if(i.eq.N) THEN
                  !This happens when j=i+1.  See if j==Value
                  CompLT=List(:,j) .arrlt. Value(:)
                  CompGT=List(:,j) .arrgt. Value(:)
                  if(.not.CompGT) then
                     tSuccess=.not.CompLT !If j's not > or <, it must be ==
                     i=j                  !j's not >, so we move up to it.
                  endif
                  FoundIndex=i
                  RETURN
               ENDIF
               !move the lower bound up
               i=N
            ELSE !it must be larger!
               !move the upper bound down
               j=N
            ENDIF
         enddo

!Here i=j=N, but .not.CompLT.  We signal failure and set FoundIndex to 1 before Min.
         FoundIndex=i-1
         RETURN
    END SUBROUTINE

end module



module BinSearch_int64_arr

    use constants
    use util_mod_comparisons, only: operator(.arrgt.), operator(.arrlt.)
    implicit none
    interface BinarySearch
        module procedure BinarySearch_int64_arr
    end interface

contains
!A binary search
! List is an ordered list of length Length
! MinInd and MaxInd are the bounds within this list of the search
! We search for Value in this list.
!  If it is found, its location is placed in FoundIndex and tSuccess is set to .TRUE.
!  If not, then the index of the largest item less than Value is placed in FoundIndex, and tSuccess is set to .FALSE.

    SUBROUTINE BinarySearch_int64_arr(Value,List,MinInd,MaxInd,FoundIndex,tSuccess)
        INTEGER :: MinInd,MaxInd,FoundIndex
        integer(kind=int64), intent(in) :: Value(:)
        integer(kind=int64), intent(in) :: List(:,:)
        INTEGER :: i,j,N
        LOGICAL :: CompLT,CompGT
        LOGICAL :: tSuccess

        i=MinInd
        j=MaxInd
        tSuccess=.false.
        do while(j-i.gt.0)  !End when the upper and lower bound are the same.
            N=(i+j)/2       !Find the midpoint of the two indices

            CompLT=List(:,N) .arrlt. Value(:)
            CompGT=List(:,N) .arrgt. Value(:)

            IF(.not.(CompLT.or.CompGT)) THEN ! If it's neither larger or smaller, it's there.
!Praise the Lord, we've found it!
                tSuccess=.true.
                FoundIndex=N
                RETURN
            ELSEIF(CompLT) THEN
               if(i.eq.N) THEN
                  !This happens when j=i+1.  See if j==Value
                  CompLT=List(:,j) .arrlt. Value(:)
                  CompGT=List(:,j) .arrgt. Value(:)
                  if(.not.CompGT) then
                     tSuccess=.not.CompLT !If j's not > or <, it must be ==
                     i=j                  !j's not >, so we move up to it.
                  endif
                  FoundIndex=i
                  RETURN
               ENDIF
               !move the lower bound up
               i=N
            ELSE !it must be larger!
               !move the upper bound down
               j=N
            ENDIF
         enddo

!Here i=j=N, but .not.CompLT.  We signal failure and set FoundIndex to 1 before Min.
         FoundIndex=i-1
         RETURN
    END SUBROUTINE

end module



module BinSearch
    use BinSearch_int
    use BinSearch_int64
    use BinSearch_double
    use BinSearch_int_arr
    use BinSearch_int64_arr
end module