binary search left and right index to find 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 O(log(N))? or will it be O(log(max(l, m)))?

Answer 1

If your task is to find the median, you could merge the arrays, which you already did, sort the entire thing, and then find the middle term using the following code:

//pretend your combined array in arrCombined
if (arrCombined.size() % 2 == 1) {
    cout << arrCombined[arrCombined.size()/2];
}
else {
    cout << (arrCombined[arrCombined.size()/2] + arrCombined[arrCombined.size()/2 - 1])/2;
}

As for your question, if you cannot understand point 1, really it's that the left and right are integers saving the left and right extents of what you are searching, meaning the left is the leftmost possible value based on your elimination, and right is the rightmost possible value. As for your second question, as trincot already said in the comments, O(log) = O(log(max(, )), so you might need to rephrase what you need.