[Question]
http://oj.leetcode.com/problems/median-of-two-sorted-arrays/
There are two sorted arrays A and B 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)).
[Thought]
第一种解法是直接归并到一个数组 O(n) 时间复杂度。
较好的解法是把这个问题看成在两个排序数组中查找Kth 元素进行折半查找，折半的时候也有不同的做法：
查找函数定义为double findKth(int A[],int m,int B[],int n,int k)
本题求median，则奇数个时直接查找中间值，偶数个时返回中间两个数的平均值。
使用两个指示器pa、pb分别指向两个数组， 且使 pa+pb=k，直观上感觉如果让这k个元素为两个数组中的前k个元素，那么pa 、pb所指的其中一个就应该是Kth.
pa
↓
A | | | | | | | |
pb
↓
B | | | | | | | | | |
最坏情况下m 、n都大于 k/2 ，让pa=k/2 pb=k/2 则每次判断A[k/2-1] B[k/2-1]的大小，舍弃一半的查找区间，并减小k ，当k=1时返回区间头的最小值。
但是实际时可能出现的情况：
[Code]
| class Solution { | |
| public: | |
| double findMedianSortedArrays(int A[], int m, int B[], int n) { | |
| int total=m+n; | |
| if(total&1) | |
| return findKth(A,m,B,n,total/2+1); | |
| else | |
| return (findKth(A,m,B,n,total/2)+findKth(A,m,B,n,total/2+1))/2; | |
| } | |
| double findKth(int A[],int m,int B[],int n,int k) | |
| { | |
| if(m>n)return findKth(B,n,A,m,k); | |
| if(m==0)return B[k-1]; | |
| if(k==1)return min(A[0],B[0]); | |
| int pa=min(m,k/2),pb=k-pa; | |
| if(A[pa-1]<B[pb-1]) | |
| return findKth(A+pa,m-pa,B,n,k-pa); | |
| else if(A[pa-1]>B[pb-1]) | |
| return findKth(A,m,B+pb,n-pb,k-pb); | |
| else return A[pa-1]; | |
| } | |
| }; |