Find Kth Largest element in two sorted arrays

11.cpp

// THIS IS IMPORTANT. 
// Using this method from leetcode.
// Let's say A[i], B[j]
// if A[i] < B[j] then kth element will be between i to n and 0 to j. so we dont need to check between 0 to i-1 and j+1 to n
// if A[i] > b[j] then kth element will be between 0 to i and j+1 to n. so we dont need to check between i+1 to n and 0 to j
// if A[j] > B[j] && A[j] < B[j+1] return A[j]
// if B[j] > A[j] && B[j] < A[j+1] return B[j]

So, Algorithm goes like this.

void kth(A,B){
   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);
}