4. Median of Two Sorted Arrays

This is a problem of kth number in two sorted arrays. Let’s look at two arrays, for m < n,
[nums1[0],nums1[1],…,nums1[m]]
[nums2[0],nums2[1],...,nums[n]]

Every time we take k numbers, i.e. we take k/2 numbers in nums1 and the rest in nums2. So we’ll have two cases:

Case 1: nums[k/2-1] <= nums[k-k/2-1] (The reason we have minus one here is when we are saying kth number in array, we count from 1 but the array index starts from 0).
we are sure that the first k/2 numbers in nums1 are smaller than the kth number and we can remove these numbers and shrink the search range. Since removing numbers in a vector take linear time, so we can use the index to present the search range in an array.

Case 2: nums[k/2-1] > nums[k-k/2-1]
We are sure that the first k-k/2-1 numbers in nums2 are smaller than the kth number and we can remove these numbers and shrink the search range.

The trick here is, the size of num1 could be smaller than k/2, so we should take i = min(k/2, e1-s1) numbers in num1 and the rest j = k -i in nums2. There are three terminations.
1. Size of num1 is larger than num2, we should swap them because the following logic assumes it.
2. Size of num1 is 0 which means we only need to find (k-1)th number in num2.
3. K is 1, which means we only need to find the smallest number in num1 and num2. We only need to return the smaller first number between num1 and num2.

When I revisited this problem, I made mistake in,
line 9-11: I was computing n1 for odd size and n2 for even side and return (n1+n2)/2.0. I should have noted that it isn’t right for odd size because in that case the result will be n1/2.0.
line 16: I missed this terminal case. Overall, I missed to add offset s1 and s2 to the i, j, and k.

1:  class Solution {  
2:  public:  
3:    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {  
4:      int n1 = nums1.size();  
5:      int n2 = nums2.size();  
6:      int k = (n1+n2) / 2;  
7:      double num1 = helper(nums1, 0, n1, nums2, 0, n2, k+1);  
8:      if ((n1+n2) % 2 == 0) {  
9:        return (num1 + helper(nums1, 0, n1, nums2, 0, n2, k))/2.0;  
10:      }  
11:      return num1;  
12:    }  
13:    int helper(vector<int> &nums1, int s1, int e1, vector<int> &nums2, int s2, int e2, int k) {  
14:      if (e1-s1 > e2-s2) return helper(nums2, s2, e2, nums1, s1, e1, k);  
15:      if (e1-s1 == 0) return nums2[s2+k-1];  
16:      if (k == 1) return min(nums1[s1], nums2[s2]);  
17:      int i = min(k/2, e1-s1);  
18:      int j = k - i;  
19:      if (nums1[s1+i-1] <= nums2[s2+j-1]) return helper(nums1, s1+i, e1, nums2, s2, e2, k-i);  
20:      else return helper(nums1, s1, e1, nums2, s2+j, e2, k-j);  
21:    }  
22:  };