题目：
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). (Hard)
Example 1:
nums1 = [1, 3]
nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 分析：
利用寻找第K个元素的辅助函数。
二分搜索的思想，每次尽量去掉数组中的一部分元素(一半左右)；
一次取K个元素出来，nums1中取 K/2个(不够就全都取出)， nums2中取 K - K/2(或nums1.size()),
判断取出的两个数组元素中的末位谁大谁小；
如果nums1[p1] < nums2[p2]，说明nums1取少了，nums2取多了，第K个元素应该在nums1的后半部分或nums2的前半部分；
如果nums1[p1] > nums2[p2], 说明nums2取少了，nums1取多了，第K个元素应该在nums2的后半部分或nums1的前半部分；
递归求解即可 。边界条件是nums1或nums2为空或K为1； 注：题目思路不是很难想到，但是处理细节有很多容易错的地方。
1.首先应确定Kth是第K个元素，对应下标应该为K-1
2.数组下标，取1/2位置时对应的哪个位置等等要注意，可以采用走样例的方式保证不出错。
3.采用了两种实现方法，一种是拷贝vector，要传参的时候注意左闭右开；
另一种是不拷贝vector，多传两个起始位置start，注意每次取元素操作时不能忘记start
第二个效率稍高，但编码中可能出错的地方也多一点。 代码1：
class Solution {
private:
double findKth(vector<int>& nums1, vector<int>& nums2, int K) { //第K个，对应下标K-1
if (nums1.size() > nums2.size()) {
return findKth(nums2,nums1,K);
}
if (nums1.size() == ) {
return nums2[K-];
}
if (nums2.size() == ) {
return nums1[K-];
}
if (K == ) {
return min(nums1[], nums2[]);
}
int s = nums1.size();
int p1 = min( K / , s);
int p2 = K - p1;
if (nums1[p1 - ] < nums2[p2 - ]) { //说明nums1取少了，kth在nums1后半段或nums2前半段
vector<int> n1(nums1.begin() + p1, nums1.end());
vector<int> n2(nums2.begin(), nums2.begin() + p2);
return findKth(n1, n2, K - p1);
}
else {
vector<int> n3(nums1.begin(), nums1.begin() + p1);
vector<int> n4(nums2.begin() + p2, nums2.end());
return findKth(n3, n4, K - p2);
}
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int s1 = nums1.size(), s2 = nums2.size();
int mid = (s1 + s2) / ;
if ( (s1 + s2) % == ) {
return (findKth(nums1, nums2, mid) + findKth(nums1, nums2, mid + )) / 2.0;
}
else {
return findKth(nums1, nums2, mid + );
}
}
};
代码2：
class Solution {
private:
double findKth(vector<int>& nums1, vector<int>& nums2, int K ,int start1, int start2) { //第K个，对应下标K-1
if (nums1.size() - start1 > nums2.size() - start2) {
return findKth(nums2,nums1,K,start2,start1);
}
if (nums1.size() - start1 == ) {
return nums2[start2 + K - ];
}
if (nums2.size() - start2 == ) {
return nums1[start1 + K - ];
}
if (K == ) {
return min(nums1[start1], nums2[start2]);
}
int s = nums1.size() - start1;
int p1 = min( K / , s);
int p2 = K - p1;
if (nums1[start1 + p1 - ] < nums2[start2 + p2 - ]) { //说明nums1取少了，kth在nums1后半段或nums2前半段
return findKth(nums1, nums2, K - p1, start1 + p1,start2);
}
else {
return findKth(nums1, nums2, K - p2, start1, start2 + p2);
}
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int s1 = nums1.size(), s2 = nums2.size();
int mid = (s1 + s2) / ;
if ( (s1 + s2) % == ) {
return (findKth(nums1, nums2, mid,,) + findKth(nums1, nums2, mid + ,,)) / 2.0;
}
else {
return findKth(nums1, nums2, mid + ,,);
}
}
};
其他与二分搜索相关的问题可以参考：
http://www.cnblogs.com/wangxiaobao/p/4915853.html