6.1. SEQUENTIAL SEARCHING
[702]
3. The following subroutine expects two parameters: p, the location of the first node, and k ≡ K, the key. After a successful search, it returns the location of the record found; otherwise, it returns zero.
| 01 | S3 | LDOU | p,p,LINK | C – S | S3. Advance. P ← LINK(P). |
| 02 | :Search | BZ | p,0F | C – S + 1[1 – S] | S4. End of file? |
| 03 | LDO | kp,p,KEY | C | kp ← KEY(P). | |
| 04 | CMP | t,k,kp | C | S2. Compare. | |
| 05 | PBNZ | t,S3 | C[S] | If K = KEY(P), terminate successfully. | |
| 06 | 0H | POP | 1,0 | Return p.  |
The running time is (5C – 2S + 3)υ + (2C – S)μ.
5. Program Q′ takes more time than Program Q if C < S + 2 + (C – S) mod 2. A successful search (S = 1) will take more time only for ...
Get The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
