LeetCode Problem

4. Median of Two Sorted Arrays Link to LeetCode Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. This problem can be converted to the problem of finding kth element, k is (A's length + B' Length)/2. If any of the two arrays is empty, then the kth element is the non-empty array's kth element. If k == 0, the kth element is the first element of A or B. For normal cases(all other cases), we need to move the pointer at the pace of half of the array size to get O(log(n)) time. The main challenge is to calculate the middle elements, we can not do the following like a regular binary search: 
            int m1 = i1+(j1-i1)/2; 
            int m2 = i2+(j2-i2)/2;
It will result in either dead loop or missing the element at the beginning. The key is we always drop <= half size of the elements. public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total = nums1.length+nums2.length; if(total%2==0){ return (getKth(nums1, 0, nums1.length-1, nums2, 0, nums2.length-1, total/2) + getKth(nums1, 0, nums1.length-1, nums2, 0, nums2.length-1, total/2-1))/2.0; }else{ return getKth(nums1,0, nums1.length-1, nums2, 0, nums2.length-1, total/2); } } //k is the index starting from 0 private int getKth(int[] nums1, int i1, int j1, int[] nums2, int i2, int j2, int k){ if(j1< i1){ return nums2[i2+k]; } if(j2< i2){ return nums1[i1+k]; } if(k==0){ return Math.min(nums1[i1], nums2[i2]); } int len1 = j1 - i1 + 1; int len2 = j2 - i2 + 1; int m1 = k*len1/(len1+len2); int m2 = k - m1 - 1; m1 += i1; m2 += i2; if(nums1[m1]< nums2[m2]){ k = k-(m1-i1+1); j2 = m2; i1 = m1+1; }else{ k = k-(m2-i2+1); j1 = m1; i2 = m2+1; } return getKth(nums1, i1, j1, nums2, i2, j2, k); }