Three hundred lookups a day
A library issues books using a text file of 20 000 membership records, one per line, in the order in which members joined. Each line holds an ID such as 004572, a name and a telephone number. When a member arrives, the clerk types the ID and the program reads the file from the beginning, comparing each line with the typed ID until it finds a match; the average wait is about four seconds and there are 300 lookups each day. A student volunteer proposes sorting the file once by ID and then searching it a different way. She has also written this input-checking loop, which staff report 'just freezes' when someone types letters instead of a number:
INPUT id WHILE id < 100000 OR id > 999999 PRINT "Invalid ID, try again" ENDWHILE
1. Compare the present search with the volunteer's proposal, using the file size and daily usage to support your answer. State the conditions her method needs in order to work.
Read the worked answer
The present search is linear. On average it examines half the records, so about 10 000 comparisons per lookup, and 20 000 in the worst case of an absent ID. At 300 lookups per day that is roughly 3 million comparisons daily, each requiring a read from the file, which is why the clerk waits about four seconds.
The volunteer is proposing a binary search on a file sorted by ID. Each comparison halves the remaining records, so the maximum number of comparisons is ceil(log2 20 000), which is 15, and the average is about 14. Daily work falls from 3 million comparisons to roughly 300 x 15 = 4 500, a few milliseconds per lookup. The one-off sort of 20 000 records costs on the order of n log2 n, about 286 000 comparisons, so it pays for itself within the first day.
Her method needs three conditions: the records must be in sorted order by the key being searched; the program must be able to jump straight to the middle record rather than reading sequentially, which in practice means loading the file into an array or maintaining an index file; and the sort must be maintained as members join.
2. Explain why the loop freezes and rewrite it so that it behaves correctly, including a limit on attempts. Point out one further check the IDs need.
Read the worked answer
The loop body never reads a new value for id. Once the typed value fails the test, the condition stays true for ever, because nothing inside the loop can change it: an infinite loop, which the staff see as a freeze. A second, quieter problem is that comparing text such as "abc" with the numbers 100000 and 999999 is either a type error or is coerced in a language-specific way, so the test itself is unreliable.
A corrected version:
attempts = 0 valid = FALSE WHILE attempts < 3 AND NOT valid INPUT id IF idIsNumeric(id) AND LENGTH(id) = 6 THEN valid = TRUE ELSE PRINT "Invalid ID, try again" attempts = attempts + 1 ENDIF ENDWHILE IF NOT valid THEN PRINT "Please see the desk supervisor"
The value is re-read inside the loop, so the condition can change; the attempt counter guarantees termination; and the check is on the characters typed rather than on a numeric comparison of an unknown type. The further check is the leading zero: 004572 is six characters but the number 4572 is four digits, so the ID should be kept and validated as a six-character string, or stored as a number and formatted with leading zeros on output.
3. A new member joins the library. What must happen for the volunteer's method to keep working, and what does that cost? Use this to judge whether binary search is the right final answer.
Read the worked answer
If the records are held in a sorted array, inserting a new member means finding the correct position and shifting every later record up by one place: about 10 000 moves on average, which is cheap in memory but must be done inside the program, not by rewriting the text file line by line. If the records are held in a sorted text file, inserting one line means rewriting the whole file, and a failure halfway through leaves it corrupt. Appending to the end is fast but breaks the sorted order that binary search depends on, so one late arrival would make some searches fail silently.
A reasonable judgement is that binary search is the right idea but the wrong data structure for a growing file. Two better options: keep the file unsorted and rebuild a sorted index file overnight, searching the small index and then jumping to the record; or move the records to a database, which maintains an index automatically as records are inserted and deleted, and handles two clerks issuing books at once. Option two is the answer if the library ever adds a second issue desk.