CareerCup

two arrays a1 and a2.
find median of a1 let say med1.
find median of a2 let say med2.
if(mid1==mid2)
return mid1
else if(mid1>mid2)
a1 = left subarray of a1
a2 = right subarray of a2
else
a1 = right subarray of a1
a2 = left subarray of a2
when single element remains in a1 or a2
that will be median

where is this code ending??

// You can find this problem in leetcode.
// There is my solution.
// I am sure this solution is right.
// And I implement test function.
// The logic is a little complex.
// I spent a whole day solving this problem.
// My solution can find Kth element in two sorted Arrays.
// Time complexity is O(log(m+n)),
// without using extra space

import java.util.Arrays;

public class Find_Kth_Element_of_Two_Sorted_Arrays {

/*
* There are two sorted arrays A and B of size m and n respectively.
* Find the kth element of the two sorted arrays.
* The overall run time complexity should be O(log (m+n)).
*/
public static int findKthofTwoArrays(int[] A,int[] B,int kth){
if(kth>=A.length+B.length||kth<0){
return Integer.MAX_VALUE;//err
}
if(kth==A.length+B.length-1){
return Math.max(A[A.length-1], B[B.length-1]);
}

if(kth<Math.min(A.length, B.length)){
return findMedianTwoArray(A,0,kth,B,0,kth);
}

if(kth==Math.min(A.length, B.length)){

if(A.length==B.length){
if(A[0]>=B[B.length-1]){
return A[0];
}
if(B[0]>=A[A.length-1]){
return B[0];
}
return findMedianTwoArray(A,1,A.length-1,B,1,B.length-1);
}
else{
if(A.length==kth){
if(A[0]>=B[A.length-1]&&A[0]<=B[A.length]){
return A[0];
}
if(B[0]>=A[A.length-1]){
return B[0];
}
if(B[A.length]<=A[0]){
return B[A.length];
}
return findMedianTwoArray(A,1,A.length-1,B,1,A.length-1);


}
else{
if(B[0]>=A[B.length-1]&&B[0]<=A[B.length]){
return B[0];
}
if(A[0]>=B[B.length-1]){
return A[0];
}
if(A[B.length]<=B[0]){
return A[B.length];
}
return findMedianTwoArray(A,1,B.length-1,B,1,B.length-1);
}

}
}

if(kth>Math.min(A.length, B.length)&&kth<Math.max(A.length, B.length)){
if(A.length>B.length){
int beginA=kth-B.length;
int endA=beginA+B.length-1;
int beginB=0;
int endB=B.length-1;
if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]&&B[beginB]<=A[endA+1]){
return B[beginB];
}
if(A[endA+1]<=B[beginB]){
return A[endA+1];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
else{
int beginA=0;
int endA=A.length-1;
int beginB=kth-A.length;
int endB=beginB+A.length-1;
if(A[beginA]>=B[endB]&&A[beginA]<=B[endB+1]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
if(B[endB+1]<=A[beginA]){
return B[endB+1];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);

}

}
if(kth==Math.max(A.length, B.length)){

int beginA=Math.max(0, A.length-B.length);
int endA=A.length-1;
int beginB=Math.max(0, B.length-A.length);
int endB=B.length-1;

if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
if(kth>Math.max(A.length, B.length)){
int beginA=kth-B.length;
int endA=A.length-1;
int beginB=kth-A.length;
int endB=B.length-1;
if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);

}

return -1;
}
public static int findMedianFourNumber(int a, int b,int c,int d){
int[] test=new int[4];
test[0]=a;
test[1]=b;
test[2]=c;
test[3]=d;
Arrays.sort(test);
return test[1];
}

public static int findMedianTwoArray(int[] A,int beginA,int endA,int[] B,int beginB,int endB){
if(endA-beginA!=endB-beginB){
return Integer.MAX_VALUE;
}
if(beginA==endA){
return Math.min(A[beginA], B[beginB]);
}
if(beginA==endA-1){
return findMedianFourNumber(A[beginA],A[endA],B[beginB],B[endB]);
}
int midA=(beginA+endA)/2;
int midB=(beginB+endB)/2;
if(A[midA]==B[midB]){
return A[midA];
}
if((endA-beginA+1)%2==0){
if(A[midA]>B[midB]){
if(A[midA]<=B[midB+1]){
return A[midA];
}
return findMedianTwoArray(A,beginA,midA,B,midB+1,endB);
}
else{
if(B[midB]<=A[midA+1]){
return B[midB];
}
return findMedianTwoArray(A,midA+1,endA,B,beginB,midB);
}
}
else{
if(A[midA]<B[midB]){
if(A[midA]>=B[midB-1]){
return A[midA];
}
return findMedianTwoArray(A,midA+1,endA,B,beginB,midB-1);
}
else{
if(B[midB]>=A[midA-1]){
return B[midB];
}
return findMedianTwoArray(A,beginA,midA-1,B,midB+1,endB);

}

}

}



/*
* for test:
* */
public static int[] creatArray(){
int [] obj=new int[(int)(Math.random()*20)+1];
for(int i=0;i!=obj.length;i++){
obj[i]=(int)(Math.random()*100);
}
Arrays.sort(obj);
return obj;
}

public static int[] creatArray(int length){
int [] obj=new int[length];
for(int i=0;i!=obj.length;i++){
obj[i]=(int)(Math.random()*100);
}
Arrays.sort(obj);
return obj;
}

public static void show(int[] test){
System.out.println();
for(int i=0;i!=test.length;i++){
System.out.print(test[i]+" ");
}
System.out.println();
}

public static int[] mergeSort(int[] o1,int[] o2){
int[] result=new int[o1.length+o2.length];
int index=0;
for(int i=0;i!=o1.length;i++){
result[index++]=o1[i];
}
for(int i=0;i!=o2.length;i++){
result[index++]=o2[i];
}
Arrays.sort(result);
return result;
}


public static void main(String[] args) {

int[] A=creatArray();
int[] B=creatArray();
int[] All=mergeSort(A,B);
System.out.print("Array A:");
show(A);
System.out.print("Array B:");
show(B);
System.out.print("Using merge O(m+n): ");
for(int i=0;i!=All.length;i++){
System.out.print(All[i]+" ");
}

System.out.println();
System.out.print("BS way O(log(m+n)): ");
for(int i=0;i!=A.length+B.length;i++){
System.out.print(findKthofTwoArrays(A,B,i)+" ");
}

}


}