4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

思路：有个很简单的做法，合并两个数组，进行排序，然后返回中位数，那这道题就变成Easy了。

题目要求在O(log (m+n))复杂度解决。可以想到用二分查找方法，先求出2个数组总共的长度，然后得出中位数的位置k，再把k / 2 - 1，分别在nums1和nums2中对比k / 2 - 1的值，若num1[k / 2 - 1]小于等于（这里把等于的情况放到一起了）num2[k / 2 - 1]，则更新num1的index，否则更新nums2的index，最后防止数组越界在更新index时要和数组长度做个比较，保留小的那个。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int length1 = nums1.length,length2 = nums2.length;
		int totalLength = length1 + length2;
		if(totalLength % 2 == 1){
			int middleIndex = totalLength / 2 +1;
			double median = getKthElement(nums1, nums2, middleIndex);
			return median;
		}else {
			int middleIndex = totalLength / 2;
			double median = (getKthElement(nums1, nums2, middleIndex) + getKthElement(nums1, nums2, middleIndex + 1)) / 2.0;
			return median;
		}
    }

	private double getKthElement(int[] nums1, int[] nums2, int k) {
		int length1 = nums1.length,length2 = nums2.length;
		int index1 = 0,index2 = 0;

		while (true){
			if(index1 == length1){
				return nums2[index2 + k - 1];
			}
			if(index2 == length2){
				return  nums1[index1 + k - 1];
			}
			if(k == 1){
				return Math.min(nums1[index1],nums2[index2]);
			}

			int half = k / 2;
			int newIndex1 = Math.min(index1 + half,length1) - 1;
			int newIndex2 = Math.min(index2 + half,length2) - 1;
			if(nums1[newIndex1] <= nums2[newIndex2]){
				k -=(newIndex1 - index1 + 1);
				index1 = newIndex1 + 1;
			}else {
				k -=(newIndex2 - index2 + 1);
				index2 = newIndex2 + 1;
			}
		}
	}
}