(Binary Search) A company database consists of 10,000 sorted names, 40% of whom

Question

(Binary Search) 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?

Explanation / Answer

Binary search - While doing the binary search the performance using single array will be log 10000 = 4

and using two array the performance will be (60/100)*log4000 + (40/100)*(log4000 + log6000 ) = 5.11

linearseach - Where as doing linear search the performance using single array will be 10000.

and using two arrray performance will be (60/100)*4000 + (40/100)*6000 = 6400 .

Therefore in binary search the good case will be using single array . Whereas using linear array the good case will be using two array , as above calculation clearly shows that .

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.