# BinSearch.F90 Source File

## Source Code

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