更完这篇我的博客和我在leetcode的刷题同步了，但是不写我一定会忘记算法，所以还是写吧。
sad T_T

闲话少絮，题目的意思是对于两个已经排好序的长度分别是m和n的数组A和B，找他们合并之后数组的中位数。要求算法复杂度为O(log(m+n))

最直接的想法是把两个数组合并然后排序然后取中位数。如果你有一个优秀的算法老师，看到复杂度的那一刻你就会想到二分。。。对没错就是二分，那么怎么二分呢？

直观地，假设m+n为奇数，我们可以想到求中位数，实际上就是求排序过后的第(m+n)/2+1个数。（若m+n为偶数，就是求中间两数的平均数，我们就不讨论了）于是，我们可以把这个问题转换成一个求第k大元素的问题。

我们假设A中元素个数和B中元素个数均大于k/2，由于A和B已经排好序了，所以我们只需要比较A[k/2-1]和B[k/2-1]，如果A[k/2-1] < B[k/2-1]则我们认为A中前k/2个元素都不是第k大的元素，可以被淘汰，于是，题目变成了一个在剩下的元素中找第k-k/2个元素的子问题。（如果B[k/2-1] < A[k/2-1]同理，如果相等，那么第k大元素就是A[k/2-1]）

我们让m>n恒成立（不成立时换一下顺序）考虑下边界情况，
当m=0时，直接返回B[k-1]
当k=1时，直接返回min(A[0], B[0]) 

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
double findkthSortedArrays(int A[], int m, int B[], int n, int k){
    if(m > n){
        return findkthSortedArrays(B, n, A, m, k);
    }
    if(m == 0){
        return B[k-1];
    }
    if(k == 1){
        return A[0]<B[0]?A[0]:B[0];
    }
    int a = (k/2)<m?k/2:m;
    if(A[a-1] < B[k-a-1]){
        return findkthSortedArrays(A+a, m-a, B, n, k-a);
    }
    else if(A[a-1] > B[k-a-1]){
        return findkthSortedArrays(A, m, B+k-a, n-k+a, a);
    }
    else{
        return A[a-1];
    }
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
    if((m+n)%2)
        return findkthSortedArrays(A, m, B, n, (m+n)/2+1);
    else
        return (findkthSortedArrays(A, m, B, n, (m+n)/2) + findkthSortedArrays(A, m, B, n, (m+n)/2+1))/2;
}

觉得眼熟的同学，对，没错，我参考了这篇文章的算法。所以1A了。

顺便说一句，这题是算法导论9.3-8的课后习题。虽然carolz坚信这题在算法课上听过，但是翻了习题笔记却找不到踪影。好吧就这样╮(╯▽╰)╭

噢，还有不知道在哪看到的：迭代为人，递归为神。orz