recursion - 如何在 fortran 中完成递归二进制搜索?
问题描述
我试图在排序数组中找到包含值 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
解决方案
有两个问题会导致您的递归搜索例程bsearch
因不需要的输出而停止,或者导致分段错误。只需按照您提供的示例中的程序执行逻辑,即可阐明问题:
1)值存在并找到,不需要的输出
首先,考虑第一个示例,其中数组b
包含i=5
您正在搜索的值(值和索引||
在下面的代码块的前两行中指出)。使用符号Rn
表示第n
'th 级递归,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
-loop被执行,被分配了正确的值,并按预期打印。但是,现在遇到了一条语句,它将控制权返回给调用程序单元——在这种情况下,首先是 R1(!),在该块之后将继续执行,从而在屏幕上打印一条初始值为 的消息。从 R0 返回到主程序时也会发生同样的情况。这解释了您看到的(不需要的)输出。else
idx
return
if-else if-else
idx=-1
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.
or.gt.
测试之一将始终评估为.true.
,这意味着low .eq. high
永远不会达到终止搜索的测试。从这一点开始,逻辑不再有效(例如high
可以小于low
),代码将继续加深递归级别,直到调用堆栈变得太大并发生分段错误。
这些解释了代码中的主要逻辑缺陷。可能的低效率是使用do
-loop 来查找包含搜索值的最低索引。考虑一种情况,您要查找的值为 eg i=8
,并且它出现在数组的最后一个位置,如下所示。进一步假设偶然地,对其位置的第一个猜测是x = high
。这意味着您的代码将立即分支到do
-loop,实际上是对几乎整个数组进行线性搜索,以找到最终结果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
-loop 中的相等测试或刚刚提到的附加测试之后。这仍然没有解决可能的线性搜索的低效率问题。
考虑到所有因素,您最好阅读查找“最左”索引的算法(例如在维基百科上或查看经过试验和测试的实现- 这里的两个示例都使用迭代而不是递归,也许是另一种改进,但相同原则适用)并将其适应 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内部过程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)
where return j
fromminloc
将是数组a
中s
可以找到的最低索引,merge
用于返回j
何时a(j) == s
和-1
否则。
推荐阅读
- javascript - 使用具有不同 var 的一个 JS 的多个输入复选框
- javascript - 尝试使用 ajax 方法将 javascript 变量发布到 php 文件:POST 但在 php 文件中的 $POST 数组中获取未定义的索引
- regex - 如何在包含表格单元格的 Word 文档选择中迭代和替换 VBA RegExp 匹配项(或其部分)?
- javascript - 直接调用功能组件
- postgresql - 从 postgresql 导出为 CSV
- verilog - 网表模拟:在这种情况下非法的“左值”
- ajax - 为什么 XMLHttpRequest 对象属性,当文件不存在时状态为 200
- python - 在 Python 逗号分隔的多重赋值中更改变量顺序
- python - 如何调试 Django 分段错误?
- android - How to efficiently make network requests from launcher activity?