Efficient Median Finding from Two Databases with Limited Queries

1. Algorithm:

• Start with two pointers, one for each database, pointing to the median of each database (initially set to n/2).
• Compare the values at the pointers in both databases.
• If the value in one database is greater than the value in the other database, then the median must be at a lower index in the database with the greater value. Update the pointer of the database with the greater value to be the median of the remaining values in that database.
• Repeat the above step until the pointers in both databases are adjacent to each other (i.e., differ by only one index).
• The median value will be the minimum of the two values at the pointers.

Pseudo-code:

1. Initialize pointers p1 and p2 to n/2 for both databases.

2. While p1 and p2 are not adjacent to each other: 3. If value at p1 in database 1 is greater than value at p2 in database 2: 4. Set p1 to p1/2. 5. Set p2 to p2 + (n-p2)/2. 6. Else: 7. Set p1 to p1 + (n-p1)/2. 8. Set p2 to p2/2.

3. Return the minimum of value at p1 in database 1 and value at p2 in database 2 as the median.

4. Correctness: The algorithm works by continuously narrowing down the possible range of the median value. At each step, it compares the values at the pointers in both databases and updates the pointers based on the comparison. Eventually, the pointers will become adjacent to each other, indicating that the median value has been found.

Proof by induction: Base case: When n = 1, there is only one value in each database, so the median is the minimum of the two values, which is correctly returned by the algorithm.

Inductive step: Assume that the algorithm correctly finds the median for a given n. Now, consider the case when n is increased by 1. The algorithm still works by comparing the values at the pointers and updating them accordingly. The maximum number of queries made is O(log(n+1)) = O(logn), which matches the desired complexity. Thus, the algorithm correctly finds the median for any value of n.

3. Complexity: The algorithm makes O(logn) queries, as it continuously halves the range of possible values at each step. Each query requires O(1) time, so the overall time complexity is O(logn). The space complexity is O(1) as we only need a constant amount of space to store the pointers and temporary variables.