Median of Two Sorted Arrays

 1 public class Solution {
 2         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3             int len = nums1.length + nums2.length;
 4             if((len&1) == 1) {
 5                 return findKth(nums1, 0, nums1.length-1, nums2, 0, nums2.length-1, len / 2 + 1);
 6             } else {
 7                 return findKth(nums1, 0, nums1.length-1, nums2, 0, nums2.length-1, len / 2) / 2 + 
 8                 findKth(nums1, 0, nums1.length-1, nums2, 0, nums2.length-1, len / 2 + 1) / 2;
 9             }
10         }
11         
12         public double findKth(int[] nums1, int left1, int right1, int[] nums2, int left2, int right2, int k) {
13             int len1 = right1 - left1 + 1;
14             int len2 = right2 - left2 + 1;
15             //always assume that m is equal or smaller than n
16             if(len1 > len2) return findKth(nums2, left2, right2, nums1, left1, right1, k);
17             if(len1 == 0) return nums2[left2 + k -1];
18             if(k == 1) return Math.min(nums1[left1], nums2[left2]);
19             //divide k into two parts 
20             int part1 = Math.min(k/2, len1);
21             int part2 = k - part1;
22             int index1 = left1 + part1 - 1;
23             int index2 = left2 + part2 - 1;
24             if(nums1[index1] < nums2[index2]) return findKth(nums1, index1+1, right1, nums2, left2, right2, k-part1);
25             else if(nums1[index1] > nums2[index2]) return findKth(nums1, left1, right1, nums2, index2+1, right2, k-part2);
26             else return nums1[index1];
27         }
28     }