[LeetCode]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)).

思考：既然是有序数组，自然想到折半搜索。每次比较去掉其中一个数组一半的数字。

class Solution {
public:
	int func(int *A,int m,int *B,int n,int k)
	{
		if(m>n) return func(B,n,A,m,k);
		if(m==0) return B[k-1];
		if(k==1) return min(A[0],B[0]);
		int pa=min(k/2,m);
		int pb=k-pa;
		if(A[pa-1]<B[pb-1]) return func(A+pa,m-pa,B,n,k-pa);
		else if(A[pa-1]>B[pb-1]) return func(A,m,B+pb,n-pb,k-pb);
		else return A[pa-1];
	}
	double findMedianSortedArrays(int A[],int m, int B[],int n) {
		// Start typing your Java solution below
		// DO NOT write main() function
		int total=m+n;
		if(total&0x1) return func(A,m,B,n,total/2+1);
		else return (double)(func(A,m,B,n,total/2)+func(A,m,B,n,total/2+1))/2;
	}
};