Description:
Given two sorted arrays (none-descending), find the Kth min element in T = O(lg(m + n)), m and n are length of two arrays, respectively.
Question:
Do not understand the algorithm below about three points:
Code: Java. Solution: Binary Search.
// k is based on 1, not 0.
public int findKthMin(int[] A, int as, int ae,
int[] B, int bs, int be, int k) {
int aLen = ae - as + 1;
int bLen = be - bs + 1;
// Guarantee the first array's size is smaller than the second one,
// which is convenient to remaining part calculation.
if (aLen > bLen) return findKthMin(B, bs, be,
A, as, ae, k);
// Base case.
if (aLen == 0) return B[bs + k - 1];
if (k == 1) return Math.min(A[as], B[bs]); // k based on 1, not 0.
// Split k,
// one part is distributed to A,
// the other part is distributed to B.
int ak = aLen < (k/2)? aLen: k/2;
int bk = k - ak;
// *k is based on 1, not 0.
int aPartitionIndex = as + (ak - 1);
int bPartitionIndex = bs + (bk - 1);
if (A[aPartitionIndex] == B[bPartitionIndex]) {
return A[aPartitionIndex];
} else if (A[aPartitionIndex] < B[bPartitionIndex]) {
// Drop the left part of A, and
// do recursion on the right part of A, and
// the entire current part of B.
k = k - ak;
return findKthMin(A, aPartitionIndex + 1, ae,
B, bs, be, k);
} else {
// Drop the left part of B, and
// do recursion on the entire current part of A, and
// the right part of B.
k = k - bk;
return findKthMin(A, as, ae,
B, bPartitionIndex + 1, be, k);
}
}
1) Assuming that A
and B
are sorted in ascending order, A[aPartitionIndex] < B[bPartitionIndex]
implies that A[i] < B[bPartitionIndex]
for all i < aPartitionIndex
.
2) You can never drop the right part of an array because you don't know where they fit in the ordering.