Question

Let \(S\) and \(T\) be two arrays of \(n\) numbers that are already in nondecreasing order. Write an algorithm that finds the median of all \(2 n\) numbers whose time complexity is in \(\Theta(\lg n)\)

Short answer

The median of the combined array of S and T can be found using a divide and conquer approach, comparing medians of arrays and discarding nearly half of the elements in each iteration. This will consistently reduce the scope of our problem to find a median by half until the base cases are reached, providing us with logarithmic time complexity, \(\Theta(\lg n)\).

Step-by-step solution

Define method

Define a method, call it 'getMedian', which can recursively work on two arrays and their halved parts. This method will take two arrays (S, T), and their size (n) as inputs.

Base Cases

Consider the following base cases: 1) If size of the arrays is 2, then the median is obtained by calculating the average of maximum of the first elements and minimum of the second elements. 2) If size of the arrays is 1, then the median is obtained by calculating the average of the two array elements.

Recursive Case

If size of the arrays is greater than 2, find the median of both arrays, say 'm1' for S and 'm2' for T. If 'm1' is equal to 'm2', then 'm1' or 'm2' is the median. If 'm1' is less than 'm2', then the median is present in one of the following two subarrays:[From first element of S to m1, From m2 to last element of T]. If 'm1' is greater than 'm2', then the median is present in one of the following two subarrays:[From m1 to last element of S, From first element of T to m2]. And the arrays are halved in each recursive call.

Continue Recursion

Halve the arrays based on the comparison of medians and recursively call the 'getMedian' method until you reach base conditions. The recursion helps in reducing the problem size by half in each recursive call, giving us the required time complexity.