COBOL 中的分界二分法。

引言

二分查找法是一种非常快速的搜索已排序表的方法。这里有一个使用 Visual COBOL 的简单示例。

在有序的一亿个数字的序列中，找到一个数字的位置需要多少步？答案大约是 26！

这说明了为问题选择正确的算法有多么重要。我想在此说明的问题是在表中找到哪些两个数字“包围”第三个数字。假设我有一个包含数字 0 10 20 30 的表，那么 15 就被 10 和 20 包围。

因为我实际上并没有在表中寻找一个数字，所以我不能使用索引。从表的开头到结尾搜索可能会非常昂贵。例如，对于一个 1 亿个元素的表，可能需要超过一亿步。

但是，如果我的表是排序的（参见 COBOL 中的声明式排序），我可以使用二分查找法。所以这是 COBOL 中的实现：

identification division.
program-id. BinaryChop.

environment division.
configuration section.

data division.
working-storage section.
01 to-find    binary-long occurs 100000000.
01 bl-1       binary-long.
01 bl-2       binary-long.
01 ln         binary-long.
01 look-4     binary-long.
01 found-prev binary-long.
01 found-next binary-long.
01 chop-pt    binary-long.
01 chop-ln    binary-long.
01 chop-ofst  binary-long.

procedure division.

   move 100000000 to ln
   perform varying bl-1 from 1 by 1 until bl-1 > ln
       compute bl-2 = bl-1 * 3
       move bl-2 to to-find(bl-1)
   end-perform
   
   move 428201 to look-4
   perform binary-chop
   
   display "Prev=" to-find(found-prev) " "
           "Next=" to-find(found-next)
   goback.
   
   binary-chop section.
   compute chop-ln = ln / 2
   compute chop-pt = chop-ln
   display "Start point: " chop-pt
   move -1 to found-prev found-next 
   perform until found-prev not = -1
           
       compute chop-ofst = chop-pt - 1
       *> Off the start
       if chop-ofst = 0
           move 0  to found-prev
           move 1  to found-next
           exit perform
       end-if
       *> found to left
       if  to-find(chop-ofst) <= look-4 
       and to-find(chop-pt)   >= look-4
           move chop-pt   to found-next
           move chop-ofst to found-prev
           exit perform
       end-if
       
       compute chop-ofst = chop-pt + 1
       *> Off the end
       if chop-ofst > ln
           move 0           to found-next
           move to-find(ln) to found-prev
           exit perform
       end-if
       *> found to right
       if  to-find(chop-ofst) >= look-4 
       and to-find(chop-pt)   <= look-4
           move chop-pt   to found-prev
           move chop-ofst to found-next
           exit perform
       end-if

       *> not found - go again
       compute chop-ln = chop-ln / 2
       if chop-ln = 0
           move 1 to chop-ln
       end-if
       display "New chop-ln: " chop-ln
       if to-find(chop-pt) < look-4
           add chop-ln      to chop-pt
       else
           subtract chop-ln from chop-pt
       end-if
       display "New chop-pt: " chop-pt
   end-perform
   .
   
end program BinaryChop.

在 Visual COBOL 中运行上面的程序（COBOL for Visual Studio - 参见此处）会产生以下输出：

Start point: +0050000000
New chop-ln: +0025000000
New chop-pt: +0025000000
New chop-ln: +0012500000
New chop-pt: +0012500000
New chop-ln: +0006250000
New chop-pt: +0006250000
New chop-ln: +0003125000
New chop-pt: +0003125000
New chop-ln: +0001562500
New chop-pt: +0001562500
New chop-ln: +0000781250
New chop-pt: +0000781250
New chop-ln: +0000390625
New chop-pt: +0000390625
New chop-ln: +0000195312
New chop-pt: +0000195313
New chop-ln: +0000097656
New chop-pt: +0000097657
New chop-ln: +0000048828
New chop-pt: +0000146485
New chop-ln: +0000024414
New chop-pt: +0000122071
New chop-ln: +0000012207
New chop-pt: +0000134278
New chop-ln: +0000006103
New chop-pt: +0000140381
New chop-ln: +0000003051
New chop-pt: +0000143432
New chop-ln: +0000001525
New chop-pt: +0000141907
New chop-ln: +0000000762
New chop-pt: +0000142669
New chop-ln: +0000000381
New chop-pt: +0000143050
New chop-ln: +0000000190
New chop-pt: +0000142860
New chop-ln: +0000000095
New chop-pt: +0000142765
New chop-ln: +0000000047
New chop-pt: +0000142718
New chop-ln: +0000000023
New chop-pt: +0000142741
New chop-ln: +0000000011
New chop-pt: +0000142730
New chop-ln: +0000000005
New chop-pt: +0000142735
New chop-ln: +0000000002
New chop-pt: +0000142733
Prev=+0000428199 Next=+0000428202

也就是说，它在一个比英国人口还多的元素的表中找到了包围元素，这非常令人印象深刻！该算法通过将表分成两半并提出问题来工作——我的数字是在下半部分（左半部分）还是上半部分（右半部分）？然后它选择适当的子表并重复该过程。通过这样做，它不断将问题的大小除以 2，直到找到解决方案。由于我们正在处理整数，需要一个陷阱来避免表的大小变为零。

compute chop-ln = chop-ln / 2
if chop-ln = 0
   move 1 to chop-ln
end-if

除此之外，还有两个陷阱来检测所查找的数字是否高于或低于表的范围。

*> Off the start
if chop-ofst = 0
   move 0  to found-prev
   move 1  to found-next
   exit perform
end-if
*> Off the end
if chop-ofst > ln
   move 0           to found-next
   move to-find(ln) to found-prev
   exit perform
end-if

所有其他算法退出条件都是在找到包围数字时。

*> found to left
if  to-find(chop-ofst) <= look-4 
and to-find(chop-pt)   >= look-4
   move chop-pt   to found-next
   move chop-ofst to found-prev
   exit perform
end-if
*> found to right
if  to-find(chop-ofst) >= look-4 
and to-find(chop-pt)   <= look-4
   move chop-pt   to found-prev
   move chop-ofst to found-next
   exit perform
end-if

最后，我们只需要代码来确定下一步应该查看哪个子表（左侧或右侧）。

if to-find(chop-pt) < look-4
   add chop-ln      to chop-pt
else
   subtract chop-ln from chop-pt
end-if