JAVA Solution solved


#1

public class Solution {
// DO NOT MODIFY BOTH THE LISTS
public double findMedianSortedArrays(final List a, final List b) {
int m = a.size();
int n = b.size();
List A = new ArrayList<>();
List B = new ArrayList<>();
if (m > n) { // to ensure m<=n
A = b;
B = a;
int tmp = m; m = n; n = tmp;
}else{
A = a;
B = b;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B.get(j-1) > A.get(i)){
iMin = i + 1; // i is too small
}
else if (i > iMin && A.get(i-1) > B.get(j)) {
iMax = i - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B.get(j-1); }
else if (j == 0) { maxLeft = A.get(i-1); }
else { maxLeft = Math.max(A.get(i-1), B.get(j-1)); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }

            int minRight = 0;
            if (i == m) { minRight = B.get(j); }
            else if (j == n) { minRight = A.get(i); }
            else { minRight = Math.min(B.get(j), A.get(i)); }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

}