# O(log(M+N)) solution without recursion

• The idea is the same as one of the top voted solutions but the code below does not use recursion.

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();

if (len % 2 != 0) {
// odd number of total elements!
return (double)findKth(nums1, nums2, len/2+1);
} else {
int midL = findKth(nums1, nums2, len/2);
int midR = findKth(nums1, nums2, len/2+1);
return (double)(midL + midR) / 2.0;
}
}

int findKth(vector<int> nums1, vector<int> nums2, int k) {
int l1 = nums1.size();
int l2 = nums2.size();
int s1 = 0, s2 = 0;

while (1) {
if (s1 >= l1) {
return nums2[s2 + k -1];
}
if (s2 >= l2) {
return nums1[s1 + k -1];
}
if (k==1) {
//cout << nums1[s1] << endl;
return min(nums1[s1], nums2[s2]);
}

int m1 = s1 + k/2 - 1;
int m2 = s2 + k/2 - 1;
int mid1 = m1 >= l1 ? INT_MAX : nums1[m1];
int mid2 = m2 >= l2 ? INT_MAX : nums2[m2];
if (mid1 > mid2) {
s2 = m2 + 1;
} else {
s1 = m1 + 1;
}
k -= k/2;
}
}
};
``````

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