(http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html)
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(lg m + lg n) solution:
1. Maintaining the invariant
i + j = k - 1,
2. 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.
code:
int findKthSmallest(int A[], int m, int B[], int n, int k)
{
assert(A && m >= && B && n >= && k > && k <= m+n); int i = (int)((double)m / (m+n) * (k-));
int j = (k-) - i; assert(i >= && j >= && i <= m && j <= n); int Ai_1 = ((i == ) ? INT_MIN : A[i-]);
int Bj_1 = ((j == ) ? INT_MIN : b[j-]);
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 > Bi) || (Ai < Bj && Ai < Bj_1)); if (Ai < Bj)
return findKthSmallest(A+i+, m-i-, B, j, k-i-);
else
return findKthSmallest(A, i, B+j+, n-j-, k-j-);
}