SEARCH ALL Requires how many comparisons? 1

[3gm]

I've always taken for granted that SEARCH ALL (binary search) takes at most O(log N) comparisons to locate an entry in a table. However, I've never delved into the specifics of any implementation in COBOL. I'm reviewing some COBOL material where the author states that to do a SEARCH ALL on a table of say 3900 entries requires between 10 and 14 comparisons.

I suspect each "probe" of the table requires maybe three comparisons (are we done yet?; Key = item; Key < (or >) item). Only two of these are key comparisons. I think, therefore, that the right "answer" is 24 key comparisons (2^12 = 4096).

Do any of you have insight on this topic, especially on specific platforms (e.g. IBM COBOL II)?

Regards.

Glenn

 

[Dimandja]

I think you'll find that all manufacturers only agree that SEARCH ALL is a binary search. Whether they use one head or more is left to the discretion of the implementer/platform and so on.

Dimandja

 

[Truusvlugindewind]

Rule of the thumb I always use:
less than 30 entries in table: use SEARCH
more than 30 entries in table: use SEARCH ALL

Dunno why. Somebody told me when I was still a junior programmer. So never use exactly 30 entries... You wouldn't know what to do

 

[webrabbit]

Most CPU's produce a tertiary result on a string compare, so a binary search need do only log₂n compares, maximum.

 

[k5tm]

Glenn,

Methinks that webrabbit is correct. The cost of the compare is great enough that the wise implementor uses all the status bits produced by the compare.

Tom Morrison

http://www.liant.com