-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMedianofTwoSortedArrays.java
More file actions
27 lines (25 loc) · 1.11 KB
/
MedianofTwoSortedArrays.java
File metadata and controls
27 lines (25 loc) · 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class MedianofTwoSortedArrays {
public double findMedianSortedArrays(int A[], int B[]) {
int n = (A.length + B.length);
if(n % 2 == 0){
return (double)(findKSortedArrays(A, 0,A.length, B, 0,B.length, n/ 2) +
findKSortedArrays(A, 0, A.length,B,0,B.length, n /2 + 1)) / 2.0;
}else{
return findKSortedArrays(A, 0,A.length, B, 0,B.length, n/2 +1);
}
}
double findKSortedArrays(int[] A, int fromA,int reA, int[] B,int fromB, int reB,int k){
if(reA > reB) return findKSortedArrays(B, fromB,reB, A, fromA,reA, k);
if(reA == 0) return B[fromB + k -1];
if(k == 1) return Math.min(A[fromA], B[fromB]);
int amid = Math.min(k/2, reA);
int bmid = k - amid;
if(A[fromA+amid-1] < B[fromB+ bmid-1]){
return findKSortedArrays(A, fromA + amid, reA - amid, B, fromB,reB, k - amid);
}else if(A[fromA+ amid-1] > B[fromB +bmid-1]){
return findKSortedArrays(A, fromA,reA, B, fromB + bmid, reB - bmid, k - bmid);
}else{
return A[fromA+ amid -1];
}
}
}