Question

A company database consists of 10,000 sorted names, 40% of whom are known as good customers and who together account for 60% of the accesses to the database. There are two data structure options to consider for representing the database: Put all the names in a single array and use binary search. 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. Demonstrate which option gives better expected performance. Does this change if linear search on an unsorted array is used instead of binary search for both options

Answer 1

Answer:

The answer is "binary search= 5.111 and Linear seacrch= 6400".

Explanation:

Following are the description of this question:

• Binary Search-The performance with single arrays is log 10000 = 4, through the use of two arrays (60/100)*log4000 + (40/100)*(log4000 + log6000) = 5.111.  
• In the linear search: while doing static searches, 10000 would be performed, and (60/100)*4000 + (40/100)*6000 = 6400 will be used with two arrays.  
• It's a special case, that will be used in one of the arrays in a binary search. Whereas good case uses linear frames, two frames are used, as indicated above.