这道题目和PAT上的1029是同一题。但是PAT1029用O(m+n)的时间复杂度（题解）就可以，这道题要求是O(log(m+n))。
这道题花费了我一个工作日的时间来思考。因为是log因而一直思考如何进行二分，想着是两个vector分别二分，但一直想不到合适的解法，就是无穷尽的if else
后来看了题解。思路是从两个有序数组中寻找第k小的数。
<1>花了很长时间在调试上，结果发现是少了一个return，期间还不停怀疑自己写递归的能力。。。要被自己打败了，调代码真是一件细小却很耗费心神的事情。
<2>对vector的使用也是醉了。
思路如下：
我们先假设nums1和nums2数组中元素个数都是大于 k/2 的，且从 0 开始编号，那么我们比较 a = nums1[k/2 - 1] 和 b = nums2[k/2 - 1]。
（1）如果 a < b 那么 nums1[0] 到 nums1[k/2 - 1] 这 k/2 个数在合并后的有序数组中，一定在第 k 小的数左边。为什么呢？
我们发现，nums1数组中比 a 小的数一共是 k/2 - 1 个。nums2数组中比 a 小的数最多有 k/2 - 1 个。因而合并以后比 a 小的数最多有k/2 - 1 + k/2 - 1 < k - 2。
也就是说 a 最多是第 k-1 小的数。所以说nums1数组前 k/2 个数可以剔除了。
（2）如果 a > b 同理，剔除掉 nums2数组前 k/2 个数。
（3）如果 a = b，a 即为所求。
每次剔除掉 k 一半个元素，因而时间复杂度是O(logk）,对于此题，k = （m+n）/2 所以时间复杂度是O（log（m+n））
考虑实际情况：
如果nums1和nums2数组中元素个数不足 k/2 个的话，一般情况下，我们只需要满足两者前面的总数目为 k 即可，原理和上述的原理是类似的，不再赘述。
此外还需要考虑特殊情况，
（1）一个数组为空，则放回另一个数组的第 k 大；
（2）k==1则直接返回min（nums1[0],nums2[0]）。
在实际实现的时候，由于输入是vector，它是一个动态数组，可以实时增加或删除元素，但是无法向普通数组/指针一样任意指定起始位置和结束为止，因而只好使用了删除操作
erase（iter1，iter2），删除[iter1,iter2)之间的元素。
class Solution {
public:
double findkth(vector<int>& nums1,vector<int>& nums2, int k)
{
int m = nums1.size(),n = nums2.size();
if(m > n)
return findkth(nums2,nums1,k);//error 1. forget the "return";
if(m == )
return double(nums2[k - ]);//error 2. write as nums2[n - 1];
if(k == )
{
return double(min(nums1[],nums2[]));
}
int pa = min(k / ,m), pb = k - pa;
if(nums1[pa - ] < nums2[pb - ])
{
nums1.erase(nums1.begin(),nums1.begin() + pa);
return findkth(nums1,nums2,k - pa);
}
else if(nums1[pa - ] > nums2[pb - ])
{
nums2.erase(nums2.begin(),nums2.begin() + pb);
return findkth(nums1,nums2,k - pb);
}
else
return double(nums1[pa - ]);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(),len2 = nums2.size();
int len = len1 + len2;
vector<int> cop1(nums1),cop2(nums2);
if(len % )
{
return findkth(nums1,nums2,len / + );
}
else
{
double t1=findkth(nums1,nums2,len / ),t2=findkth(cop1,cop2,len / + );
return (t1 + t2) / ;
}
}
};
删除vector的元素需要①额外备份一下数组，②删除操作。无谓的耗时，因而重新实现成手动标记数组的起始位置。只需要在上面实现方法的基础上 + star就可以了，原理都是一样的。
class Solution {
public:
double findkth(vector<int>& nums1,int st1,int ed1,vector<int>& nums2, int st2,int ed2,int k)
{
int m = ed1 - st1,n = ed2 - st2;
if(m > n)
return findkth(nums2,st2,ed2,nums1,st1,ed1,k);//error 1. forget the "return";
if(m == )
return double(nums2[st2 + k - ]);//error 2. write as nums2[n - 1];
if(k == )
{
return double(min(nums1[st1],nums2[st2]));
}
int pa = min(k / ,m), pb = k - pa;
if(nums1[st1 + pa - ] < nums2[st2 + pb - ])
{
return findkth(nums1,st1 + pa,ed1,nums2,st2,ed2,k - pa);
}
else if(nums1[st1 + pa - ] > nums2[st2 + pb - ])//error 3. forget the "st2 +";
{
return findkth(nums1,st1,ed1,nums2,st2 + pb,ed2,k - pb);
}
else
return double(nums1[st1 + pa - ]);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(),len2 = nums2.size();
int len = len1 + len2;
if(len % )
{
return findkth(nums1,,len1,nums2,,len2,len / + );
}
else
{
double t1 = findkth(nums1,,len1,nums2,,len2,len / ),t2 = findkth(nums1,,len1,nums2,,len2,len / + );
return (t1 + t2) / ;
}
}
};