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

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.
O(logK)
http://www.quora.com/Algorithms/Given-two-sorted-lists-of-size-m-and-n-what-is-the-fastest-algorithm-for-computing-the-kth-smallest-element-in-the-union-of-the-two-lists
https://coderwall.com/p/gumhbg
Compare the 2 middle elements.
Assume A[k/2] < B[k/2].
Reduce the problem to finding the k/2th element in A[k/2:] and B[0:k/2].
private static void getKthSmallestInTwoArrays(int[] a, int[] b, int k) {
int lowA = 0, lowB = 0, highA = k - 1, highB = k - 1;
if (a.length < (k - 1)) {
highA = a.length - 1;
}
if (b.length < (k - 1)) {
highB = b.length - 1;
}
if ((highA + highB) < k) {
// insufficient elements
return;
}
int midA = 0, midB = 0;
int result = 0;
while (k >= 0) {
midA = lowA + (highA - lowA) / 2;
midB = lowB + (highB - lowB) / 2;
if (a[midA] >= b[midB]) {
// it means the first midA elements of A are all greater than
// first midB elements of B
// it means that the kth smallest lies in second half of B OR
// first half of A
k = k - (midB - lowB + 1);
result = b[midB];
highA = midA - 1;
lowB = midB + 1;
} else if (a[midA] < b[midB]) {
// it means the first midB elements of B are all greater than
// first midA elements of A
// it means that the kth smallest lies in second half of A OR
// first half of B
k = k - (midA - lowA + 1);
result = a[midA];
highB = midB - 1;
lowA = midA + 1;
}
if (k == 0)
break;
}
System.out.println(result);
}

O(k) : when k is small
Using two pointers, you can traverse both arrays without actually merging them, thus without the extra space. Both pointers are initialized to point to head of A and B respectively, and the pointer that has the 
smaller of the two is incremented one step. The k-th smallest is obtained by traversing a total of k steps. 
 O(lg m + lg n):

int findKthSmallest(int A[], int m, int B[], int n, int k) {

  assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

  

  int i = (int)((double)m / (m+n) * (k-1));

  int j = (k-1) - i;

  assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);

  // invariant: i + j = k-1

  // Note: A[-1] = -INF and A[m] = +INF to maintain invariant

  int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);

  int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);

  int Ai   = ((i == m) ? INT_MAX : A[i]);

  int Bj   = ((j == n) ? INT_MAX : B[j]);

  if (Bj_1 < Ai && Ai < Bj)

    return Ai;

  else if (Ai_1 < Bj && Bj < Ai)

    return Bj;

  assert((Ai > Bj && Ai_1 > Bj) ||

         (Ai < Bj && Ai < Bj_1));

  // if none of the cases above, then it is either:

  if (Ai < Bj)

    // exclude Ai and below portion

    // exclude Bj and above portion

    return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);

  else /* Bj < Ai */

    // exclude Ai and above portion

    // exclude Bj and below portion

    return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);

}

Extended:
http://algorithmsforever.blogspot.com/2011/11/kth-smallest-in-union-of-arrays.html

Given two sorted arrays of size M and N. Find Kth smallest element in the union of the two arrays in constant space. (i.e. without using additional space).

Solution :

The Kth element will be found within first K elements of both arrays, so we consider only these elements or whole array if size is less than K
We use recursive procedure. We compare (K/2)th element in arrays A(0 K) and B(0 K)
if A(K/2) < B(K/2) we recursively find (K-K/2)th smallest element in A(K/2+1 K) and B(0 K/2) eliminating first K/2 elements from A
else if A(K/2) > B(K/2) we recursively find (K-K/2)th smallest element in B(K/2+1 K) and A(0 K/2) eliminating first K/2 elements from B
if A(K/2) == B(K/2) return A(K/2) as answer

Boundaries must be checked in the procedure

Complexity :

• Time : log N + log M (Please check if its min(log N, log M) rather than this)
• Space : O(1)

Code :

void kth_smallest(int[] A, int M, int[] B, int N, int K, int &result){

int a_high = (M < K) ? M : K;
int b_high = (N < K) ? N : K;

result = find_kth(A, 0, a_high, B, 0, b_high, K); 

}

int find_kth(int[] A, int a_low, int a_high, int[] B, int b_low, int b_high, int K){

// boundary cases
if(a_low > a_high)

return B[b_low + K - 1];

if(b_low > b_high)

return A[a_low + K - 1];

int mid = (K+1)/2;  // finding ceiling of K/2

if(A[mid] == B[mid])

return A[mid];

else if(A[mid] < B[mid])

return find_kth(A, a_low + mid+1, a_high, B, b_low, b_low + mid, mid);

else if(A[mid] > B[mid])

return find_kth(A, a_low, a_low + mid, B, b_low + mid + 1, b_high, mid);

}

void kth_smallest_linear(int[] A, int M, int[] B, int N, int K, int &result){

int i=0, j=0;
for( ; K; K--){

if(i >= M){

result = B[j + K - 1];
break;

}
if(j >= N){

result = A[i + K - 1];
break;

}
if(A[i] == B[j]){

result = A[i++];
j++;

}
else

result = (A[i] < B[j]) ? A[i++] : B[j++];

}

}

Read full article from Find the k-th Smallest Element in the Union of Two Sorted Arrays | LeetCode