【自留】寻找两个正序数组的中位数，时间复杂度O(log(m+n))
先看题：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
时间复杂度O(m+n)的解法很好想，依次步进遍历两个数组，每一次哪个数组的值小就步进哪一个，直到走到中位数位置。需要注意的点有：
某个数组已经遍历完了。
在总个数为偶数的情况下（即中位数为中间俩数平均值），需要记录最新两个元素的值，并且在return的时候将int转换为double。
接下来记录时间复杂度O(log(m+n))的解法。
很显然用的应该是二分，但要对两个数组在不合并的情况下进行二分。
我们先看总元素为偶数的情况，数组1有4个元素，数组2有6个元素，总计10个，应该分成左边5个右边5个。此时可以发现，我们需要的两个中位数8和9，即为两个数组左边元素的最大值（即数组1左最大值8和数组2左最大值6的最大值）和两个数组右边元素的最小值。
当总元素个数为奇数的时候，我们采用左边比右边多一个的方式（右边多也行），可以发现中位数即为两个数组左边元素的最大值（6和7中的7）。
那么在知道了成功分割之后如何得到答案，接下来的问题就是如何分割。
我们设数组1长度为m，数组2长度为n，那么左边就应该有 (m+n+1)/2 个元素，记为allLeft（注意整型除法向0取整，因此无论m+n的奇偶都用这个公式）。在已知了左边一共有多少个元素时，确定了数组1当中左边有 i 个元素，那么数组2左边一定有allleft - i 个元素。
其次，用什么条件来判断分割线已经是正确的了呢？
因为俩数组本身就是有序的，我们只需要在数组之间比较就行，即 数组1的左最大 < 数组2的右最小，并且 数组2的左最大 < 数组1的右最小。在上图为6<8， 7<15。
那么在二分的过程中只需要上述条件任取一个来缩小范围即可。如上图，12<8不成立，因此在数组1的分割线应该右移。
在分割完成后取出上述提及的分割线左右总计4个元素再根据奇偶进行计算返回即可。
细节：
在二分的时候需要注意是否会进入死循环
无论是选取数组左边最大值作为i，j还是右边最小值作为i，j，在对应+1-1操作的时候都需要考虑是否存在下标越界的情况。需要控制right和left的取值和中间位置计算方法来避免越界。
在分割完成后，在取分割线左右值的时候需要注意越界问题（存在某个数组全在左边或者全在右边的情况）。
部分代码（留档）：
包括 二分，取左右值，返回 部分。
int left = 0;
int right = m;
while (left < right){
int i = left + (right - left + 1) / 2; //+1防止当left=i时进入死循环
int j = allLeft - i;
//计算出nums1数组左边的数量i即可得知nums2数组的j；i和j分别为俩数组分割线后第一个元素（右边最小值）
if (nums1[i-1] < nums2[j]){
//如果数组1的左最大 小于 数组2的右最小，说明分割线在数组1的位置还能右移
left = i;
}
else{
right = i-1;
}
}
int i = left;
int j = allLeft - i;
int nums1LeftMax = i == 0 ? INT_MIN : nums1[i-1]; //防止越界
int nums1RightMin = i == m ? INT_MAX : nums1[i];
int nums2LeftMax = j == 0 ? INT_MIN : nums2[j-1];
int nums2RightMin = j == n ? INT_MAX : nums2[j];
if ((m+n) % 2 == 1 ){
return max(nums1LeftMax, nums2LeftMax);
}
else{
return (double)(max(nums1LeftMax,nums2LeftMax) + min(nums2RightMin, nums1RightMin)) / 2;
