Bracketing Binary Chop in COBOL

Introduction

Binary Chop (binary search) is a really fast way of searching a sorted table. Here is a simple example of how to do it with Visual COBOL.

How many steps does it take to find where a number fits in an ordered series of one hundred million numbers? The answer is around 26!

This illustrates how picking the correct algorithm for a problem makes all the difference. The problem I want to illustrate here is finding which two numbers in a table 'bracket' a third number. Consider that I have a table with the numbers 0 10 20 30 in it, then 15 is bracketed by 10 and 20.

Because I am not actually looking for a number in the table itself, I cannot use an index. Just searching from one end of the table to the other could be very expensive. In the example of a 100 000 000 element table - it could take more then one hundred million steps.

However, if my tabled is sorted (see Declarative Sorting in COBOL), I can use the binary chop search algorithm. So here it is in 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.

Running the above program in Visual COBOL (COBOL for Visual Studio - see here) produces the following output:

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

Which is to say that it has found the bracketing elements out of a table with more elements than there are humans in Britain, is quite impressive! The algorithm functions by splitting the table in half and asking the question - is my number in the bottom (left) half or the top (right) half. It then picks the appropriate sub-table and repeats the process. By so doing, it repeatedly divides the problem size by 2 until the solution is found. Because we are working with integers, there needs to be a trap to avoid the table size going to zero:

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

Along with this, there are two traps to detect if the number looked for is above or below the range of the table:

*> 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

All the other algorithm exit conditions are where the bracketing numbers are found:

*> 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

Finally, we just need the code to work out which sub-table (left or right) to look in next:

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