# 3 solutions: use a helper getkth, and use binary search

• 1 & 2. O(log(m+n))

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size(), k = m+n-1 >> 1;
if (m+n & 1) return getkth(nums1, nums2, k);
return (getkth(nums1, nums2, k) + getkth(nums1, nums2, k+1)) * 0.5;
}
private:
int getkth(vector<int>& a, vector<int>& b, int k) {  // 0 index
int m = a.size(), n = b.size(), i = 0, j = 0;
while (k) {
int p = k-1>>1;
if (i+p >= m || j+p < n && a[i+p] > b[j+p])
j += p+1;
else
i += p+1;
k -= p+1;
}
return i >= m || j < n && a[i] > b[j] ? b[j] : a[i];
}
};

//another way of writing getkth
int getkth(vector<int>& a, vector<int>& b, int k) { // 0 index
int m = a.size(), n = b.size(), i = 0, j = 0;
while (m && n && k) {
int p = k-1>>1, ii = min(m-1, p), jj = min(n-1, p);
if (a[i+ii] > b[j+jj])
j += jj+1, n -= jj+1, k -= jj+1;
else
i += ii+1, m -= ii+1, k -= ii+1;
}
if (!m) return b[j+k];
if (!n) return a[i+k];
return min(a[i], b[j]);
}
``````
1. O(log(min(m,n))) binary search on smaller array. I tried write a seperate getkth helper at first, then there're just too many corner cases to deal with such that writing a generalized version seems tedious.
``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) return findMedianSortedArrays(nums2, nums1);
bool odd = m+n & 1;
int k = m+n-1>>1;
if (!m)
return odd ? nums2[k] : 0.5*nums2[k] + 0.5*nums2[k+1];
if (nums1[0] >= nums2[k]) {
if (odd) return nums2[k];
return 0.5*nums2[k] + 0.5*(k==n-1 || nums2[k+1]>nums1[0] ? nums1[0] : nums2[k+1]);
}
if (k >= m) {
if (nums2[k-m] >= nums1[m-1])
return odd ? nums2[k-m] : 0.5*nums2[k-m] + 0.5*nums2[k-m+1];
else if (nums1[m-1] <= nums2[k-m+1])
return odd ? nums1[m-1] : 0.5*nums1[m-1] + 0.5*nums2[k-m+1];
} else if (nums1[m-1] <= nums2[0])
return odd ? nums1[m-1] : 0.5*nums1[m-1] + 0.5*nums2[0];

int l = 0, h = m-1;
while (l <= h) {
int i = l+h >> 1, j = k-i-1;
if (nums1[i] < nums2[j]) {
if (nums1[i+1] >= nums2[j])
return odd ? nums2[j] : 0.5*nums2[j] + 0.5*min(nums1[i+1], nums2[j+1]);
l = i+1;
} else {
if (nums2[j+1] >= nums1[i])
return odd ? nums1[i] : 0.5*nums1[i] + 0.5*min(nums2[j+1], nums1[i+1]);
h = i-1;
}
}
return -1;
}
};
``````

• hey yijiexu3,
I am not able to understand this code

``````int getkth(vector<int>& a, vector<int>& b, int k) {  // 0 index
int m = a.size(), n = b.size(), i = 0, j = 0;
while (k) {
int p = k-1>>1;//what's the idea here to choose p like that ?
if (i+p >= m || j+p < n && a[i+p] > b[j+p])
j += p+1;//since a[i+p]>b[j+p] , we are increasing b's next comparison?
else
i += p+1;
k -= p+1;
}
return i >= m || j < n && a[i] > b[j] ? b[j] : a[i];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.