Binary Search (variation), Time complexity: O(log(min(m,n)))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
28
29
30
31
32
33
34
35
36
37
38
39class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int x = A.length;
int y = B.length;
if (x > y) {// to ensure x<=y
int[] temp1 = A;
A = B;
B = temp1;
int temp2 = x;
x = y;
y = temp2;
}
int low = 0;
int high = x;
while (low <= high) {
int partitionx = (low + high) / 2;
int partitiony = (x + y + 1) / 2 - partitionx; // (x+y+1) because the sum of length either odd or even.
int maxLeftx = (partitionx == 0) ? Integer.MIN_VALUE : A[partitionx - 1];
int minRightx = (partitionx == x) ? Integer.MAX_VALUE : A[partitionx];
int maxLefty = (partitiony == 0) ? Integer.MIN_VALUE : B[partitiony - 1];
int minRighty = (partitiony == y) ? Integer.MAX_VALUE : B[partitiony];
if (maxLeftx <= minRighty && maxLefty <= minRightx) {
if ((x + y) % 2 == 0) {
return (double) (Math.max(maxLeftx, maxLefty) + Math.min(minRightx, minRighty)) / 2;
} else {
return (double) Math.max(maxLeftx, maxLefty);
}
} else if (maxLeftx > minRighty) {
high = partitionx - 1;
} else {
low = partitionx + 1;
}
}
return -1;// error occurs
}
}