12,402,666 members (75,440 online)
alternative version

11.2K views
6 bookmarked
Posted

# Bracketing Binary Chop in COBOL

, 18 Jun 2010 CC (ASA 2.5)
 Rate this:
COBOL already has SEARCH ALL, but what if you want to find table values which bracket a searched value - here is the solution.

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

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
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
else
subtract chop-ln from chop-pt
end-if```

## Share

 Web Developer United Kingdom
I am now a Software Systems Developer - Senior Principal at Micro Focus Plc. I am honoured to work in a team developing new compiler and runtime technology for Micro Focus.

My past includes a Ph.D. in computational quantum mechanics, software consultancy and several/various software development and architecture positions.

For more - see

blog: http://nerds-central.blogspot.com

## You may also be interested in...

 First Prev Next
 COBOL - How Quaint ! Dave Cross18-Jun-10 1:22 Dave Cross 18-Jun-10 1:22
 Visual COBOL alex turner18-Jun-10 0:40 alex turner 18-Jun-10 0:40
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Jul-16 21:45 Refresh 1