Given records , each has a key , respectively. Given a key, consider searching for the corresponding record. For a given query key , if there is a key where () then the search is successful and the record is returned, otherwise the search fails and the failure is returned.
Let be the probability where the query key is , and be the probability of the search failure. The computation time is almost proportional to the number of comparisons with . Let us calculate the average number of comparisons and the maximum number of comparisons .
(1) Consider a sequential search that compares with keys from to .
(a) Obtain and when .
(b) Prove that when .
(2) Consider a binary search after sorting the keys. Let ( is a natural number), and moreover, one comparison will determine whether or .
(a) Obtain and for each case of , when .
(b) Obtain and as a function of when .
(3) Consider a search using a hash table. The records are inserted into the hash table of size using the hash function . Let the key values each be .
(a) Draw the structure of the hash table by choosing an appropriate method for avoiding collision.
(b) Obtain and when .
(4) Describe in general the advantages and disadvantages of sequential search, binary search and search using a hash table.