My solution tries binary search on index i in first array and then I can know how much to take from B. I know it is log n and was wondering why is the intended solution in log(n + m)
double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
int n = A.size(), m = B.size();
int lo = -1, hi = n - 1; // all values of i
int even = ((n + m) & 1) ^ 1; // is it odd case median.
while (lo <= hi) {
int mid = (lo + hi) / 2; // last element taken from A
int r = n - mid - 1; // total element left from A
int needed = (n + m) / 2 - r; // all element needed from B to complement.
// taken too much from the right of A
// printf("taken up to %d with r %d and needs %d\n", mid, r, needed);
if (needed < 0) {
lo = mid + 1;
continue;
}
// taken too little from the right of A
if (needed > m) {
hi = mid - 1;
continue;
}
int i = mid;
int j = m - needed - 1; // index of last element in B
int left_max = i > -1 ? A[i] : INT_MIN;
if (j >= 0) left_max = max(left_max, B[j]);
int right_min = min(j + 1 >= m ? INT_MAX : B[j + 1], i + 1 >= n ? INT_MAX : A[i + 1]);
// printf("%d %d\n", left_max, right_min);
if (left_max <= right_min) {
double median = left_max;
if (even) {
median += right_min;
return median / 2;
} else return median;
} else {
// we have to reupdate our indexeses.
if (i > -1 && left_max == A[i]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
return -1;
}