I posted the formulæ for match-seeking binary and linear search in a 'related' thread.
Following Knuth, the standard figure of merit for match-seeking binary search if the total number of ternary comparison operations required to search a set with 2n + 1 argments. For the n keys k(1) < k(2) < . . . < k(i) < . . .< k(n) they are o 1 such that a < k(1), o n such that a = k(i), i = 1, 2, . . . , n, o n - 1 such that k(j) < a < k(j+1), j = 1, 2, . . . , n - 1, o 1 such that a > k(n). The cutover-point for Knuth's match-seeking binary search implemented in an assembly language that makes a signum-like ternary-comparison instruction available is n > 4, for which binary search is faster than linear search. In general my view is that binary search done by a trusted subroutine is almost always preferable to linear search: tables get bigger much more frequently than they get smaller. For perforce hand-coded searches EJ's ROT is a good one, but the situations in which it is not possible to use a subroutine and an externalized, separately assembled table or BST are infrequent. -- John Gilmore, Ashland, MA 01721 - USA t. ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to [email protected] with the message: INFO IBM-MAIN
