Median of two sorted arrays

Question

Two sorted arrays A and B are given having size l and m respectively. Our task is to find the median of these two sorted arrays combined. Suppose the length of the combined array is n i.e. n = l + m.By definition the median will be greater than half of the elements and less than the other half.

Suppose A[i] is the median. Then since A is sorted so

                            A[i] >= A[k] for all k = 0 to i - 1

and it will also be greater than j = ⌈n/2⌉- (i - 1) elements in B as i + j must be equal to ⌈n/2⌉.

                      A[i] >= B[k] for all k = 0 to ⌈n/2⌉- (i - 1)

If A[i] is not the median, then depending on whether A[i] is greater or less than B[j] and B[j + 1], you know that A[i] is either greater than or less than the median.

Thus binary search for A[i] can be done here. Following is the pseudo code I have found from a website:

                MEDIAN-SEARCH(A[1 . . l], B[1 . . m], left,right)

                 if left > right:
                   MEDIAN-SEARCH(B, A, max(1, ⌈n/2⌉ − l), min(m, ⌈n/2⌉))

                 i = ⌊(left + right)/2⌋

                 j = ⌈n/2⌉ - i

                 if (j = 0 or A[i] > B[j]) and (j = m or A[i] <= B[j + 1])
                   return A[i]

                 else if (j = 0 or A[i] > B[j]) and j != m and A[i] > B[j + 1]
                   return MEDIAN-SEARCH(A, B, left, i − 1)

                 else
                   return MEDIAN-SEARCH(A, B, i + 1, right)

The initial call to find median will be

                 MEDIAN-SEARCH(A[1..l], B[1..m], max(1, ⌈n/2⌉ − m), min(l, ⌈n/2⌉))         

My question here is:

1. I am not able to visualize intuitively how left and right initial values are being used in the code above.
2. What will be time complexity of the algorithm? Will it be log O(N)? or will it be log O(max(l, m))?

Answer 1

The source hinted that it is by the definition of median and outlined how to verify an element in $O(1)$.

If $l > m$, $left = \lceil (l - m) / 2 \rceil$, $right = \lceil (l + m) / 2 \rceil$. Else, $left = 1$, $right = l$.

The median is guaranteed to be found in $A[left..right]$ using that range, or if not then trivially found in $B$.

As this is essentially a binary search, it runs in $O(log(min(l, m))$.

If $A$ and $B$ are not sorted, you can combine both and run quickselect in $O(log(max(l, m))$ instead.