You are interested in analyzing some hard-to-obtain data from two separate datab

Question

You are interested in analyzing some hard-to-obtain data from two separate databases. Each database
contains n numerical values — so there are 2n values in total — and you may assume that no two
values are the same. You’d like to determine the median of this set of 2n values, which we will define
here to be the nth smallest value.
However, the only way you can access these values is through queries to the database. In a single
query, you can specify a value k to one of the two databases, and the chosen database will return the
kth smallest value that it contains. Since queries are expensive, you would like to compute the mediuan
using as few queries as possible.
Give an algorithm that finds the median value using at most O(log n) queries. You may assume
that n is a power of two.

Explanation / Answer

//find median of joint database

//Let d1 and d2 be the two databases

ptr1 = ptr2 = n/2 //query pointers

for val = 2 to log n do

median1 = Query_ database (d1, ptr1) // median for database d1

median2 = Query_ database (d2, ptr2) // median for database d2

if median1 > median2 then

ptr1 ? ptr1 ? n/2 val //process upper half of the database d1

ptr2 ? ptr2 + n/2 val //process lower half of the database d2

else

ptr1 ? ptr1 + n/2 val

ptr2 ? ptr2 ? n/2 val

end if

end for

return min (median1, median2)

The algorithm takes : O(log n) time

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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