1. You are interested in analyzing some hard-to-obtain data from two sepa- rate
ID: 3732175 • Letter: 1
Question
1. You are interested in analyzing some hard-to-obtain data from two sepa- rate databases. Each database contains n numerical values-so there are 2n values 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 databases. 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 median using as few queries as possible. Give an algorithm that finds the median value using at most O(log n) queries.Explanation / Answer
For acheiving the complexity as O(log n), we should use the binary search approach here. We will divide n into 2 parts at each iteration.
Case 1 - if Database1.Query(i) < Database2.Query(j), then the elements from 1 to i inclusive of Database1 must exist in the first n elements.We will now be finding the (n - i)th element (which is equal to n/2) in the Database1(from i + 1 to n) and Database2(from 1 to n).
Case 2 - if Database1.Query(i) > Database2.Query(j), We will follow the same steps as above but we "cut" the Database2 database now.
Thus, every time we will "cut" n / 2 elements from anyone of the databases based on the case satisfied, the next time will cut (n / 2) / 2 elements from that database, and so on.. until n = 1, the smaller one from Database1.Query(1) and Database2.Query(1) is the "nth element".
Then will return the current nth element from the other database.
The algo will be like below :
int medianDB(DBHandler* database1, int i, DBHandler* database2, int j, const int n, int k) {
if((n - i) > (n - j))
{
return medianDB(database2, j, db1, i, n, k);
}
if(i >= n)
{
return database2->Query(j + k);
}
if(j >= n)
{
return database1->Query(i + k);
}
if(k == 1)
{
return min(database1->Query(i + 1), database2->Query(j + 1));
}
int amed = min(k / 2, n - i);
int bmed = k - amed;
if(database1->Query(i + amed) <= database2->Query(j + bmed))
{
return medianDB(database1, i + amed, database2, j, n, k - amed);
}
return medianDB(database1, i, database2, j + bmed, n, k - bmed);
}
int medianofDatabase(DBHandler* database1, DBHandler* database2, int n)
{
return medianDB(database1, 0, database2, 0, n, n);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.