Problem 1: Search Algorithms
A company database has 10,000 customers sorted by last name, 30% of whom are known to be
good customers. Under typical usage of this database, 60% of lookups are for the good customers.
Two design options are considered to store the data in the database:
1. Put all the names in a single array and use binary search.
2. Put the good customers in one array and the rest of them in a second array. Only if we do
not find the query name on a binary search of the first array do we do a binary search of the
second array.
Given these options, answer the following.
i. Calculate the expected worst-case performance for each of the two structures above, given
typical usage. Which of the two structures is the best option?
ii. Suppose that over time the usage of the database changes, and so a greater and greater
fraction of lookups are for good customers. At what point does the answer to part i change?
iii. Under typical usage again, suppose that instead of binary search we had used linear search.
What is the expected worst-case performance of each of the two structures and which is the
better option? Where is the cross-over this time?