Open congr opened 6 years ago
LeetCode AC
class Solution {
public double findMedianSortedArrays(int[] X, int[] Y) {
int x = X.length, y = Y.length;
if (x > y) return findMedianSortedArrays(Y, X);
int low = 0, high = x;
while(low <= high) {
int px = (low+high)/2;
int py = (x + y + 1)/2 - px; // !!!
int maxlx = (px == 0) ? Integer.MIN_VALUE: X[px-1];
int minrx = (px == x) ? Integer.MAX_VALUE: X[px];
int maxly = (py == 0) ? Integer.MIN_VALUE: Y[py-1];
int minry = (py == y) ? Integer.MAX_VALUE: Y[py];
if (maxlx <= minry && maxly <= minrx) {
if ((x+y)%2 == 0) return ((double)Math.max(maxlx, maxly) + Math.min(minrx, minry)) / 2.0;
else return Math.max(maxlx, maxly);
} else if (maxlx > minry)
high = px - 1;
else low = px + 1;
}
return 0.0;
}
}
https://leetcode.com/problems/median-of-two-sorted-arrays/description/