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

package ListNode;

public class findMedianSortedArrays {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

class Solution4 {

	public double findMedianSortedArrays(int[] nums1, int[] nums2) {

		// 1.先比较两个数组的长度，让nums1存放较短的数组
		// 为了保证需要查找对比的分界线两边的数的下标不越界，我们必须从较短的数组上寻找分割线的位置
		if (nums1.length > nums2.length) {
			int[] temp = nums1;
			nums1 = nums2;
			nums2 = temp;
		}

		int m = nums1.length;
		int n = nums2.length;

		// 2.分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
		// 如果是总元素个数是偶数个那么左右两边相等，如果是奇数个，那个左边多一个元素
		// m+n 为奇数，分割线要求左侧有 (m+n)/2 + 1 个元素
        // m+n 为偶数，分割线要求左侧有 (m+n)/2     个元素
        // 两种情况其实可以统一写作 (m+n+1)/2，表示对(m+n)/2向上取整
		int totalLeft = (m + n + 1) / 2;

		// 3.在 nums1 的区间 [0, m] 里查找恰当的分割线，保证分割线左边的数始终比右边的小
		// 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
		int left = 0;
		int right = m;

		// 二分查找法
		/*
		 * 分割线左侧元素小于等于分割线右侧元素。由于两个数组均为正序数组，则只需要要求： 
		 * nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]； 
		 * 由于该条件等价于在[0, m]中找到最大的i使得nums1[i-1] <= nums2[j]，
		 * 因此可以使用二分查找。（证明：假设我们已经找到了满足条件的最大i， 使得nums1[i-1] <= nums2[j]，
		 * 那么此时必有nums[i] > nums2[j]，进而有nums[i] > nums2[j-1]）。 
		 * 当 i 从 0 ∼m 递增时，A[i−1] 递增，B[j]递减，所以一定存在一个最大的i满足A[i−1]≤B[j]；
		 * 如果i是最大的，那么说明 i+1 不满足。将 i+1 带入可以得到A[i]>B[j−1]，也就是B[j−1]<A[i]，
		 * 就和我们进行等价变换前 i 的性质一致了（甚至还要更强）。
		 * 
		 */
		while (left < right) {
			// i就是nums1数组分割线右边第一个数的下标
			int i = left + (right - left + 1) / 2;  
			// j就是nums2数组分割线右边第一个数的下标
			int j = totalLeft - i;

			if (nums1[i - 1] > nums2[j]) {
				// 下一轮搜索的区间 [left, i - 1]
				right = i - 1;
			} else {
				// 下一轮搜索的区间 [i, right]
				left = i;
			}
		}

		// 退出循环时left=right，表示最终nums1中分割线的位置
		int i = left;
		int j = totalLeft - i;

		//判断极端情况
        int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];  //nums1分割线左边没有元素
        int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];  //nums2分割线左边没有元素
        int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];     //nums1分割线右边没有元素
        int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];     //nums2分割线右边没有元素

		if (((m + n) % 2) == 1) {
			return Math.max(nums1LeftMax, nums2LeftMax);
		} else {
			//返回左边数组中最大的值和右边数组中最小的值的和
			return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
		}
	}
}