public static int kthSmallestRec(int k,int[] A,int[] B){
  int n=A.length;
  int m=B.length;
  if (n > m)   return kthSmallestRec(k,B,A);
  int k=(n + m - 1) / 2;
  int l=0, r=Math.min(k,n);
  while (l < r) {
    int midA=(l + r) / 2;
    int midB=k - midA;
    if (A[midA] < B[midB])     l=midA + 1;
 else     r=midA;
  }
  int a=Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE,k - l >= 0 ? B[k - l] : Integer.MIN_VALUE);
  if (((n + m) & 1) == 1)   return (double)a;
  int b=Math.min(l < n ? A[l] : Integer.MAX_VALUE,k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE);
  return (a + b) / 2.0;
}

public static int kthSmallestRec ( int k , int [ ] A , int [ ] B ) { int n = A . length ; int m = B . length ; if ( n > m ) return kthSmallestRec ( k , B , A ) ; int k = ( n + m - 1 ) / 2 ; int l = 0 , r = Math . min ( k , n ) ; while ( l < r ) { int midA = ( l + r ) / 2 ; int midB = k - midA ; if ( A [ midA ] < B [ midB ] ) l = midA + 1 ; else r = midA ; } int a = Math . max ( l > 0 ? A [ l - 1 ] : Integer . MIN_VALUE , k - l >= 0 ? B [ k - l ] : Integer . MIN_VALUE ) ; if ( ( ( n + m ) & 1 ) == 1 ) return ( double ) a ; int b = Math . min ( l < n ? A [ l ] : Integer . MAX_VALUE , k - l + 1 < m ? B [ k - l + 1 ] : Integer . MAX_VALUE ) ; return ( a + b ) / 2.0 ; }
binary search of a and b o ( lg m + lg n ) make i + j = k - 1 if bj - 1 < ai < bj , then ai must be the k - th smallest , or else if ai - 1 < bj < ai , then bj must be the k - th smallest .
