The question which is faster depends in detail upon 1) whether binary search is implemented in assembly language, in which case ternary comparison operations are available, or in a statement-level language other that PL/I, in which case ternary comparisons must be simulated using a binary decision tree, and
2) whether for linear search the table searched is ordered. For Knuth's match-seeking binary search of an ordered set M(n) = 2[(n + 1)q +2e] where n is the table size, q = floor[log2(n + 1)], and e = n - (2^q -1) Linear search of an ordered table is given by L(n) = 2[n(n + 1)/2] = n(n + 1) Then for n = 1, 2, 3, 4 ,5, 6, 7 M(n) = 0, 3, 8, 13, 20, 27, 34, 41 L(n) = 0, 2, 6, 12, 20, 30, 42, 56 L(n) < M(n) for n < 4, L(n) = M(n) for n = 4, L(n) > M(n) for n > 4, L(n) >> M(n) for large n. For linear search of an unordered table U(n) = 2[L(n)] There are complications. In most SLPLs Knuth's scheme should be replaced by a glb- or lub-seeking one specialized for match seeking, etc., etc. Qualitatively, binary search is superior to linear search when n is non-trivial. It is not, that is, a good replacement for if-then-else. Both are, of course, radically inferior to branch-table based schemes, e.g., the one used to implement the C switch staterment and the analogous PL/I select group, that do no searching at all. John Gilmore, Ashland, MA 01721 - USA ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to [email protected] with the message: INFO IBM-MAIN
