# search algorithms performance

A company database has 10,000 customers sorted by last name, 20% 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. If we do not find the query name on a binary search of the first array, 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?

My approach:

In the worst case for binary search, when the value is not in our array, the algorithm must continue iterating until the span has been made empty; this will have taken at most $log2(N)+1$ iterations. In our situation, it is $log2(10000)+1 = 13.28+1 = 14.28 = 15$? Not sure i'm on the right track. How does 20% of 10000 are good customers and 60% lookups are for good customers taking into account this problem?

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?

Let $X \equiv$ the number of iterations needed in the worst case for the second scenario. Notice that: $$X = \begin{cases} \lceil \log_2(0.2 \cdot 10000) \rceil + 1 = 12 &\text{if customer is good} \\ \lceil \log_2(0.8 \cdot 10000) \rceil + 1 = 14 &\text{otherwise} \\ \end{cases}$$ and: $$P(X = x) = \begin{cases} 0.6 &\text{if }x = 12 \\ 0.4 &\text{otherwise} \\ \end{cases}$$ Hence, the average number of iterations is: $$E(X) = \sum_x x \cdot P(X = x) = 12(0.6) + 14(0.4) = 12.8$$ which is smaller than $15$, and so is more efficient than the second scenario.