Find the k-th Smallest Element in the Union of Two Sorted Arrays

Problem:
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

Solution:

O(m + n): Merge the arrays and return the k-th element. Also requires O(m+n) memory.

O(k): Maintain two indexes for each array and perform the merge procedure w/o actually merging the arrays. I.e. just traverse them both and return the k-th element.

O(log m + log n): Given i and j as indexes in A and B respectively, the smallest of A[i] and B[j] is the element that we search for if  i+j = k-1 AND the element (say, A[i]) satisfies B[j-1] < A[i] < B[j] (or vice versa for B[j].) And since the arrays are sorted, we can perform "binary searches" on them, or rather divide them by half. See Links for the code.

O(log k): This is similar to the previous method, but is done by maintaining the "left" and "right" borders of the smallest subarray of size 2*k in an array that would have been the result of merging the arrays. We do not perform the actual merge operation, we only do binary searches on the bottom parts of the arrays:

int findKthInSortedArrays(int A[], int B[], int k) {
    if (A == null)  A = new int[0];
    if (B == null)  B = new int[0];
    int nA = A.length;
    int nB = B.length;
    if (nA == 0 && nB == 0) return Integer.MIN_VALUE;

    int l = k - Math.min(k, nB);
    int r = Math.min(k, nA);

    while(l <= r) {
        int i = l + (r - l) / 2;
        int j = k - i;

        int a_i = (i < nA) ? A[i] : Integer.MAX_VALUE;
        int a_i_prev = (i > 0) ? A[i-1] : Integer.MIN_VALUE;
        int b_j = (j < nB) ? B[j] : Integer.MAX_VALUE;
        int b_j_prev = (j > 0) ? B[j-1] : Integer.MIN_VALUE;

        if (a_i >= b_j_prev && b_j >= a_i_prev) {
            return Math.max(a_i_prev, b_j_prev);
        }

        if (a_i < b_j_prev) {
            l = i + 1;
        } else {
            r = i - 1;
        }
    }

    return Integer.MIN_VALUE;
}

Complexity:

time - O(log n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/136/find-the-k-th-smallest-element-in-the-union-of-two-sorted-arrays