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
if chop-ofst = 0
move 0 to found-prev
move 1 to found-next
exit perform
end-if
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
if chop-ofst > ln
move 0 to found-next
move to-find(ln) to found-prev
exit perform
end-if
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
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:
if chop-ofst = 0
move 0 to found-prev
move 1 to found-next
exit perform
end-if
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:
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
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
