我如何在fortran中完成递归二进制搜索？

Question

我正在尝试在排序数组中找到包含值i的最小索引。如果不存在此i值，我希望返回-1。我正在使用二进制搜索递归子例程。问题是我无法真正停止此递归，并且得到了很多答案（一个是对，其余是错误的）。有时我会收到一个称为“细分错误：11”的错误，但我并没有得到任何结果。

由于我在主程序中已经有一个排序数组，所以我试图删除此调用random_number，但是它不起作用。

 program main
  implicit none
  integer, allocatable      :: A(:)
  real                      :: MAX_VALUE
  integer                   :: i,j,n,s, low, high
  real                      :: x

  N= 10                !size of table
  MAX_VALUE = 10

  allocate(A(n))

  s = 5          ! searched value
  low = 1        ! lower limit
  high = n       ! highest limit


  !generate random table of numbers (from 0 to 1000)
  call Random_Seed
  do i=1, N
     call Random_Number(x)  !returns random x >= 0 and <1
   A(i)= anint(MAX_VALUE*x)
  end do

 call bubble(n,a)
 print *,' '
 write(*,10) (a(i),i=1,N)
 10 format(10i6)

 call bsearch(A,n,s,low,high)

 deallocate(A)

end program main

排序子例程：

subroutine sort(p,q)

    implicit none
    integer(kind=4), intent(inout)      :: p, q
    integer(kind=4)                  :: temp

    if (p>q) then
       temp = p
       p = q
       q = temp
    end if
    return
end subroutine sort

气泡子例程：

subroutine bubble(n,arr)

 implicit none
 integer(kind=4), intent(inout)        :: n
 integer(kind=4), intent(inout)        :: arr(n)
 integer(kind=4)                       :: sorted(n)
 integer                               :: i,j

do i=1, n
   do j=n, i+1, -1
      call sort(arr(j-1), arr(j))
   end do
end do
return

end subroutine bubble

recursive subroutine bsearch(b,n,i,low,high)

   implicit none
   integer(kind=4)       ::    b(n)
   integer(kind=4)       ::    low, high
   integer(kind=4)       ::    i,j,x,idx,n
   real(kind=4)          ::    r

   idx = -1

   call random_Number(r)
   x = low + anint((high - low)*r)

   if (b(x).lt.i) then
   low = x + 1
   call bsearch(b,n,i,low,high)

   else if (b(x).gt.i) then
      high = x - 1
      call bsearch(b,n,i,low,high)
   else
   do j = low, high
    if (b(j).eq.i) then
       idx = j
       exit
    end if
    end do
  end if

 ! Stop if high = low
    if (low.eq.high) then
    return
   end if

   print*, i, 'found at index ', idx
   return

   end subroutine bsearch

目标是获得与线性搜索相同的结果。但是我得到了这些答案之一。

排序表：

     1     1     2     4     5     5     6     7     8    10

       5 found at index            5
       5 found at index           -1
       5 found at index           -1

或如果找不到该值

   2     2     3     4     4     6     6     7     8     8  

   Segmentation fault: 11

Answer 1

有两个问题导致您的递归搜索例程bsearch停止，并出现不必要的输出，或者导致分段错误。只需遵循提供的示例中程序的执行逻辑，就可以说明问题：

<< [1]值存在并找到，不需要的输出首先，考虑第一个示例，其中数组b包含要搜索的值i=5（下面代码块的前两行中用||指出的值和索引）。使用符号Rn表示第n个级别的递归，L和H表示上下限，x表示当前索引估算值，代码的给定运行可以看起来像这样：

b(x): 1     1     2     4    |5|    5     6     7     8    10
x:    1     2     3     4    |5|    6     7     8     9    10
R0:   L                                         x          H
R1:   Lx                                  H
R2:         L                       x     H

    5 found at index            5
    5 found at index           -1
    5 found at index           -1

在R0和R1中，b(x).lt.i中的测试b(x).gt.i和bsearch按照预期的目的来缩短搜索间隔。在R2中，执行do分支中的else循环，为idx分配了正确的值，并按预期进行打印。 
但是，现在遇到一个return语句，该语句将return control to the calling program unit-在这种情况下是第一个R1（！），在该位置将在if-else if-else块之后恢复执行，从而在屏幕上显示一个带有首字母的消息idx=-1的值。从R0返回主程序时也会发生同样的情况。这解释了您看到的（不需要的）输出。
[2）值不存在，分段错误

其次，考虑导致分段错误的示例。使用与以前相同的符号，可能的运行如下所示：

b(x): 2     2     3     4     4     6     6     7     8     8
x:    1     2     3     4     5     6     7     8     9     10
R0:   L                 x                                   H
R1:                           L                       x     H
R2:                           L     x           H
R3:                          LxH
R4:                           H     xL
.
.
.

Segmentation fault: 11

在R0至R2中，搜索间隔再次按预期减小。但是，在R3中，逻辑失败。由于数组i中不存在搜索值b，因此.lt.或.gt.测试之一将始终计算为.true.，这意味着永远不会达到low .eq. high终止搜索的测试。从现在开始，逻辑不再有效（例如high可以小于low），并且代码将继续加深递归级别，直到调用堆栈变得太大并发生分段错误为止。
这些解释了代码中的主要逻辑缺陷。可能的效率低下是使用do循环查找包含搜索值的最低索引。考虑一种情况，其中您正在寻找的值是i=8，并且它出现在数组的最后位置，如下所示。进一步假设偶然，对其位置的第一个猜测是x = high。这意味着您的代码将立即分支到do循环，实际上，该循环几乎对整个数组进行了线性搜索，以找到最终结果idx=9。尽管正确，但预期的二进制搜索反而变成了线性搜索，可能会导致性能降低。
b(x): 2     2     3     4     4     6     6     7    |8|    8
x:    1     2     3     4     5     6     7     8    |9|    10
R0:   L                                                     xH

    8 found at index            9

解决问题
至少，应该将low .eq. high测试移至bsearch例程的开头，以便在定义无效边界之前停止递归操作（然后，您需要进行其他测试以查看是否找到了搜索值）或不）。另外，请在搜索成功后即在do循环中的相等性测试或上述其他测试之后立即通知成功的搜索。这仍然不能解决可能的线性搜索效率低下的问题。
考虑到所有因素，您可能最好阅读用于查找
“ leftmost”索引的算法（例如，在Wikipedia上或在tried and tested implementation上查找-这里的两个示例都使用迭代而不是递归，也许是另一种改进，但应用相同的原理）并使之适应Fortran，这看起来可能是这样的（仅显示新代码，...引用示例中的现有代码）：
module mod_search
  implicit none
  contains
    ! Function that uses recursive binary search to look for `key` in an
    ! ordered `array`. Returns the array index of the leftmost occurrence
    ! of `key` if present in `array`, and -1 otherwise
    function search_ordered (array, key) result (idx)
      integer, intent(in) :: array(:)
      integer, intent(in) :: key
      integer :: idx

      ! find left most array index that could possibly hold `key`
      idx = binary_search_left(1, size(array))

      ! if `key` is not found, return -1
      if (array(idx) /= key) then
        idx = -1
      end if

      contains

        ! function for recursive reduction of search interval
        recursive function binary_search_left(low, high) result(idx)
          integer, intent(in) :: low, high
          integer             :: idx
          real                :: r

          if (high <= low ) then
            ! found lowest possible index where target could be
            idx = low
          else
            ! new guess
            call random_number(r)
            idx = low + floor((high - low)*r)
            ! alternative: idx = low + (high - low) / 2

            if (array(idx) < key) then
              ! continue looking to the right of current guess
              idx = binary_search_left(idx + 1, high)
            else
              ! continue looking to the left of current guess (inclusive)
              idx = binary_search_left(low, idx)
            end if
          end if
        end function binary_search_left

    end function search_ordered

    ! Move your routines into a module
    subroutine sort(p,q)
       ...
    end subroutine sort

    subroutine bubble(n,arr)
      ...
    end subroutine bubble
end module mod_search

! your main program
program main
  use mod_search, only : search_ordered, sort, bubble    ! <---- use routines from module like so
  implicit none
  ...

  ! Replace your call to bsearch() with the following:
  ! call bsearch(A,n,s,low,high)
  i = search_ordered(A, s)
  if (i /= -1) then
    print *, s, 'found at index ', i
  else
    print *, s, 'not found!'
  end if
  ...
end program main

最后，根据您的实际用例，您也可以考虑使用Fortran intrinsic procedure minloc，省去了自己实现所有这些功能的麻烦。在这种情况下，可以通过在主程序中进行以下修改来完成：
minloc

从! i = search_ordered(a, s)  ! <---- comment out this line
j = minloc(abs(a-s), dim=1) ! <---- replace with these two
i = merge(j, -1, a(j) == s)
返回的j将是数组minloc中可以找到a的最低索引，并且当s和merge时，merge用于返回j 。