leetcode : 4 Median of Two Sorted Arrays

Questions:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

class Solution {

public:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

}

};

Solution:

1. Transform the question to "Find the kth smallest element from two sorted array",   where k depens on whether m + n is an odd or even number

2. How to find the kth smallest element from two sorted array :

      2.1. Compare the two elements in the middle (not median) of nums1 and nums2,   mid = (start + end)/2

                 indices at nums1:         start1 , start1 + 1.... ...mid1,  mid1 + 1, ...   end1         

  indices at nums2:         start2 , start2 + 1.... ...mid2,  mid2 + 1, ...   end2         

       2.2  Decrease and conquer 

Suppose nums1[mid1] >= nums2[mid2],  depends on the value of k,   either the fraction larger than mid1 or the fraction smaller than mid2 can be dropped,  update k when necessary

       2.3 Trick on drop

                 Drop middle element along with the fraction, to avoid infinite loop and guarantee boundary case

       2.4  Boundary case

When one array is empty

Source:   (didn't consider the case when input two arrays are empty)

class Solution {
	double getKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k) {
		int mid1, mid2;
		while (true) {
			if (end1 < start1)
				return nums2[start2 + k - 1];
			if (end2 < start2)
				return nums1[start1 + k - 1];
			mid1 = (start1 + end1) / 2;
			mid2 = (start2 + end2) / 2;
			if (nums1[mid1] >= nums2[mid2]) {
				if (k <= mid1 - start1 + mid2 - start2 + 1)
					end1 = mid1 - 1;
				else {
					k = k - (mid2 + 1 - start2);
					start2 = mid2 + 1;
				}
			}
			else {
				if (k <= mid1 - start1 + mid2 - start2 + 1)
					end2 = mid2 - 1;
				else {
					k = k - (mid1 + 1 - start1);
					start1 = mid1 + 1;
				}				
			}
		}
	}
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int sizeNums1 = nums1.size();
		int sizeNums2 = nums2.size();
		double res = getKth(nums1, 0, sizeNums1 - 1, nums2, 0, sizeNums2 - 1, (sizeNums1 + sizeNums2) / 2 + 1);
		if ((sizeNums1 + sizeNums2) % 2)
			return res;
		else
			return (res + getKth(nums1, 0, sizeNums1 - 1, nums2, 0, sizeNums2 - 1, (sizeNums1 + sizeNums2) / 2 )) / 2;
	}
};