search.f90

Go to the documentation of this file.

!##############################################################################
!     ________  _____  ______________ 
!    / ____/  |/  / / / /_  __/  _/ / 
!   / /_  / /|_/ / / / / / /  / // /  
!  / __/ / /  / / /_/ / / / _/ // /___
! /_/   /_/  /_/\____/ /_/ /___/_____/                                     
!
! Copyright 2020 Bharat Mahajan
!
! Licensed under the Apache License, Version 2.0 (the "License");
! you may not use this file except in compliance with the License.
! You may obtain a copy of the License at
!
!    http://www.apache.org/licenses/LICENSE-2.0
!
! Unless required by applicable law or agreed to in writing, software
! distributed under the License is distributed on an "AS IS" BASIS,
! WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
! See the License for the specific language governing permissions and
! limitations under the License.
!
!
!##############################################################################
 
    
module search
 
    use fmutilbase
    
    implicit none
 
    integer, parameter :: max_iterations = 50
    
    abstract interface
        pure function func(x) result(y)
            import :: wp
            implicit none
            real(wp), intent(in) :: x
            real(wp) :: y
        end function func
    end interface
    
    contains
    
    
    pure function binarysearch(SortedX, SortedDataArray)
 
        !import :: WP
    
        implicit none    
    
        real(wp), dimension(1:), intent(in)  :: sortedx
        real(wp), dimension(:), intent(in)  :: sorteddataarray
        integer, dimension(size(SortedX)) :: binarysearch
 
        integer :: lb, ub, a, b, m, n, ctr, xloc
        real(wp) :: x
        
        ! initialize
        lb = 1
        ub = size(sorteddataarray)
        m = lb
        
        ! for each element
        do ctr = 1, size(sortedx)
        
            ! element to search for
            x = sortedx(ctr)
            
            ! current interval. Note we assume that the array of the elements
            ! to search for is also a sorted array.
            a = m
            b = ub
            
            ! loop for finding the element
            do
                ! size of the current interval
                n = b - a + 1
        
                ! mid-point
                m = floor((n+1)/2.0) + (a-1)
        
                if (x < sorteddataarray(m)) then    
                    ! search the lower half
                    b = m
                    cycle
                elseif (x > sorteddataarray(m) .AND. (m+1) /= b) then
                    ! search the upper half
                    a = m
                    cycle
                else
                    ! We either have found the exact match 
                    ! Or x lies in between Data(m) and Data(m+1)
                    xloc = m
                    exit
                end if        
            end do
 
            ! save the location of the current element
            binarysearch(ctr) = xloc
        end do
    
    end function binarysearch    
    
    
    
end module search