MVSFORUMS.com

[tcurrier]

Hello,

I wouldn't normally do a binary search on a table with less than 5 rows of data, but by accident, I found out that the binary search doesn't work if this is the case.

I also have a problem when the table has more than 10 occurrences 'defined'.

I've tried this with both the VS COBOL II and Enterprise COBOL compilers, same results.

Does anyone know what could be going on with this ?

[Terry_Heinze]

I'm afraid you're going to have to prove to me that binary search does not work for fewer than 5 elements or more than 10. Please show the table and your code and do not key it in; use copy and paste to prevent typos.
_________________
....Terry

[dbzTHEdinosauer]

[tcurrier]

OK, here's a quote from one of my co-workers:

"I am not sure.. but I think (I might have read it some where, not necessarily for COBOL) for a binary search to work well, the table should be filled at least 50%."

It looks like he's right. I changed my program to 20 occurrences of the table and 'filled' 10 of them.... (Table was originally initialized to spaces). The binary search worked. I then ran it with 9 tables entries filled instead of 10. It didn't work.

[dbzTHEdinosauer]

Blind leading those who can't see.

If you want anything except harassment, you need to supply us with some data layout and the code and we will tell you why your results and opinion are wrong.

Binary seaches become more effecient that scans when the number of items exceeds 50 (somewhere in that area)

the efficency of a binary search has nothing todo with the percentage of items filled / declared. -

For a binary search to work:
an item must be higher on the coallating sequence than the preceding item.

Cobol is not the only language that has a binary search. Binary search is an algorithm, suggest you spend your time reading about facts instead of theory.
Once you understand how a binary search functions,
you may wish that you had not created this thread.
_________________
Dick Brenholtz
American living in Varel, Germany

[tcurrier]

Thanks for your input, but I have a roll program that I need to complete by tomorrow and I don't have time to get into a lot of research and long discussions about how binary searches work.

I failed to mention before that the data that the table is being filled from is coming from an external file, so there will not always be the same number of entries in the table. Therefore, I got around the 'problem' by
using the 'occurs depending on' clause in the table definition. INPUT-SUB
is equal to the number of records read from the input file and loaded into the table.

[jsharon1248]

I suspect you defined the table with a fixed number of elements, that is, a table without an ODO clause. I also suspect that you're initializing the keys for all the 'unused' high order elements to high-values. If that's the case, the binary search might work in some cases, but not others. The problem is that you might not want the 'unused' elements to participate in the search, but COBOL doesn't have any way of knowing they're 'unused'. Setting the key to high-values might give you the impression that these elements won't participate in the search, but that is not valid solution for a binary search. Note the word unique in the Binary Search notes from the manual. You're better off specifying an ODO clause when utilizing a binary search.

[tcurrier]

Here is a simplified example:

[tcurrier]

But yes, to answer your ODO question... as I mentioned in a previous post, the ODO clause takes care of the 'problem' ....

[dbzTHEdinosauer]

a binary search starts at item number (total items declared / 2).
compares. if the search key is less than, then the next item checked is item number ((total items declared - (total items declared /2) ) / 2.

in other words, then the 2nd item to check is either half way back or half way to the end.

had you populated the-table with high-values instead of spaces, it would have found TOM with 4 entries.

Since you are using ODO (which you should, since you have an undertermined amount of items) you will be ok.
_________________
Dick Brenholtz
American living in Varel, Germany

[tcurrier]

Humm, you're right.
Initializing the 'fixed' table to high-values does produce the correct result.
Thanks !

[dbzTHEdinosauer]

you are welcome.
had i taken the time to explain in my first post what I wrote in the third,
probably would have saved us both time.

apologize for being abrupt (maybe even rude).
_________________
Dick Brenholtz
American living in Varel, Germany

[Terry_Heinze]

tcurrier,
I don't think you would even have asked this question if you had read the COBOL Language Reference Manual concerning SEARCH ALL or the Programming Guide concerning Handling Tables.
_________________
....Terry

[tcurrier]

You're right. My bad.