【题意】

给两个有序数组，寻找两个数组组成后的中位数，要求时间复杂度为O(log(n+m))。

【题解】

感觉这道题想法非常妙！！

假定原数组为a，b，数组长度为lena，lenb。

那么中位数一定是第k = （lena + lenb + 1）/ 2小的数，如果是数组长度和是偶数的话就是第k = （lena + lenb + 1）/ 2小和第k = （lena + lenb + 2）/ 2小的数，所以我们可以把问题转化为求第k小的数。

然后分别对a，b找第k / 2小的数，假如a[k / 2 - 1]和b[k / 2 -1] ，如果a[k / 2 - 1 > b[k / 2 - 1]，那么就说明b[k / 2 - 1]必然不是我们要找到的答案，也就是说k / 2 - 1之前的数字我们都可以排除掉，下一次b数组的开始位置变成k  / 2，然后下一次就要寻找第k = k - (k / 2)小的数（此处默认从0开始）了，然后不断递归，直到k = 1，也就是说当前指向的数就是我们要找的数，这时只要取两者最小值即可。

【代码】

1 class Solution {
2 public:
3 double findMedianSortedArrays(vector& nums1, vector& nums2) {
4 int len1 = nums1.size();
5 int len2 = nums2.size();
6 int k1 = (len1 + len2 + 1) / 2;
7 int k2 = (len1 + len2 + 2) / 2;
8 double ans = (findk(0, len1 - 1, nums1, 0, len2 - 1, nums2, k1) * 1.0 + findk(0, len1 - 1, nums1, 0, len2 - 1, nums2, k2) * 1.0) / 2;
9 return ans;
10 }
11 int findk(int st1, int en1, vector& nums1, int st2, int en2, vector& nums2, int k)
12 {
13 int len1 = en1 - st1 + 1;
14 int len2 = en2 - st2 + 1;
15 // 使nums1的长度保持小于nums2
16 if (len1 > len2)
17 return findk(st2, en2, nums2, st1, en1, nums1, k);
18 if (len1 == 0)return nums2[st2 + k - 1];
19 if (k == 1)return min(nums1[st1], nums2[st2]);
20
21 int i = st1 + min(len1, k / 2) - 1;
22 int j = st2 + min(len2, k / 2) - 1;
23 if (nums1[i] > nums2[j])
24 return findk(st1, en1, nums1, j + 1, en2, nums2, k - (j - st2 + 1));
25 else
26 return findk(i + 1, en1, nums1, st2, en2, nums2, k - (i - st1 + 1));
27 }
28 };