题目描述

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)).

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

思路

首先划重点， 两数组有序 、 复杂度须为O(log (m+n)) 。刚看到题时，第一反应是将两数组合并为一个，然后排序取中位数，这样方法由于有排序存在，最低复杂度在(m+n)O(log (m+n))级别；或是不用合并排序，遍历两个数组同时数数，也可以取到中位数，复杂度是O(m+n)级别。但此题要求基本O(log (m+n))，也就是限制了这两种解法。而这时如果注意到 数组有序 的条件，再加上 log 级别的时间复杂度，很容易想到二分法（二分查找）。常规的二分法是在单个有序数组上实现的，但思想是通用的，这题最终也是用二分法的思想AC的，下面在详细介绍思路之前，首先复习一下二分法及其思想。

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半，以这个数组建立一个平衡二叉树，则在数组中的查找过程其实是和平衡二叉树中的查找过程是等价的。最坏情况下，查找的复杂度就是平衡二叉树的树高O(log n)。

属性 说明
数据结构 数组（有序）
最坏时间复杂度 O(log n)
最优时间复杂度 O(1)
平均时间复杂度 O(log n)
迭代空间复杂度 O(1)
递归空间复杂度 O(log n)
二分查找二分查找

回来说这题，这题其实可以转化为查找第k大的数，中位数只是一个特定的k。下面说如何在双数组中查找第k大的数。 二分法是一次删除掉当前搜索范围的一半，这一半是一定不会包含目标元素的。利用这个思想来看如何在双数组中查找第k大的数，首先我们假设给定数组A和B的元素个数都大于k/2，于是我们将A的第k/2个元素和B的第k/2个元素进行比较，会有以下三种情况：

A[k/2 - 1] == B[k/2 - 1]
A[k/2 - 1] < B[k/2 - 1]
A[k/2 - 1] > B[k/2 - 1]

当A[k/2-1] == B[k/2-1]时，表示已经找到了A ∪ B中第K大的数，直接返回；

当A[k/2-1] < B[k/2-1]时，表示A[k/2-1]不可能大于A ∪ B中第K大的数，那么由于数组有序，A[0]到A[k/2-1]这个范围的数都不可能大于A ∪ B中第K大的数，删除这个搜索范围，继续在剩余的搜索范围A[k/2]到A[end]和B中进行搜索。

A[k/2-1] > B[k/2-1]同理。

AC代码 Version.1
findMedianSortedArrays.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int len1 = nums1.size(), len2 = nums2.size();
    int k = (len1 + len2) / 2 + 1;
    if((len1 + len2) & 0x1)
        return find_Kth_InSortedArrays(nums1.begin(), nums2.begin(), len1, len2, k);
    else
        return ( find_Kth_InSortedArrays(nums1.begin(), nums2.begin(), len1, len2, k - 1) 
                + find_Kth_InSortedArrays(nums1.begin(), nums2.begin(), len1, len2, k ) ) / 2.0;
}

int find_Kth_InSortedArrays(vector<int>::const_iterator pLeft, vector<int>::const_iterator pRight, int lLen, int rLen, int k)
{
    if(k < 1 || k > lLen + rLen)
        return -1;
    if(lLen > rLen)
        return find_Kth_InSortedArrays(pRight, pLeft, rLen, lLen, k);
    if(0 == lLen)
        return *(pRight + k - 1);
    if(1 == k)
        return std::min(*pLeft, *pRight);
    int lMid = std::min(k >> 1, lLen);
    int rMid = k - lMid;
    if(*(pLeft + lMid - 1) == *(pRight + rMid - 1))
        return *(pLeft + lMid - 1);
    else if(*(pLeft + lMid - 1) < *(pRight + rMid - 1))
        return find_Kth_InSortedArrays(pLeft + lMid, pRight, lLen - lMid, rLen, k - lMid);
    else 
        return find_Kth_InSortedArrays(pLeft, pRight + rMid, lLen, rLen - rMid, k - rMid);
}

顺便

查资料时，看到这么一段话

然《编程珠玑》的作者Jon Bentley曾在贝尔实验室做过一个实验，即给一些专业的程序员几个小时的时间，用任何一种语言编写二分查找程序（写出高级伪代码也可以），结果参与编写的一百多人中：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。 也就是说：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：而且高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。 你能正确无误的写出二分查找代码么？不妨一试，关闭所有网页，窗口，打开记事本，或者编辑器，或者直接在本文评论下，不参考上面我写的或其他任何人的程序，给自己十分钟到N个小时不等的时间，立即编写一个二分查找程序。

Excuse Me？ 90%程序员写不出无BUG的二分查找程序？我也试了试，照着10分钟来的，没测试，不知道对否，也不知是否属于90%

binarySearch.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
//找到返回数组中下标，找不到则返回-1
int binarySearch(const vector<int>& nums, int start, int end/*real end idx 's next*/, int target)
{
    if (start >= end)
        return -1;
    int mid = start + (end - start - 1) / 2;			/*real mid idx*/
    if (nums[mid] == target)
        return mid;
    else if (target < nums[mid])
        return binarySearch(nums, start, mid, target);
    else
        return binarySearch(nums, mid + 1, end, target);
}
int targetSearch(const vector<int>& nums, int target) {
    return binarySearch(nums, 0, nums.size(), target);
}