学步园

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

代码的主体比较好写，三个地方卡了我一会。一个是其中有一个长度可能为0，这时候要单独处理；而是直接int相加除以2，结果答案不对；第三点也是最烦的一点，就是这个第K大和下标的转换，数来数去的搞不清楚哪里应该+1，-1什么的，很烦。

class Solution {
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		assert(A&&B);
		assert(m>0||n>0);
		if (m==0||n==0)
		{
			int * C=m==0?B:A;
			int t=m==0?n:m;
			return singleArray(C,t);
		}
		if ( m < n )
			return solve(A,m,B,n,0,m-1);
		else
			return solve(B,n,A,m,0,n-1);	
	}
	double solve(int a[],int m,int b[],int n,int l,int r)
	{
		int half=(m+n)>>1;
		if ( l > r )
			return solve(b,n,a,m,max(0,half-m),min(half,n-1));

		int mid = (l+r)>>1;
		int k= half-(mid);

		if ( get(a,m,mid) > get(b,n,k) )
			return solve(a,m,b,n,l,mid-1);
		else if ( get(a,m,mid) < get(b,n,k-1) )
			return solve(a,m,b,n,mid+1,r);
		else
		{
			if ( (m+n)%2 == 0)
			{
				return (double(a[mid])+max(get(a,m,mid-1),get(b,n,k-1)))/2;
			}
			else
			{
				return a[mid];
			}
		}
	}
	int get(int a[],int n,int k)
	{
		if ( k<0 )
			return INT_MIN;
		else if ( k>=n)
			return INT_MAX;
		else
			return a[k];
	}
	double singleArray(int* a ,int n)
	{
		assert(a&&n>0);
		int mid=n>>1;
		if ( n%2==0)
		{
			return (double(a[mid])+a[mid-1])/2;
		}
		else
			return a[mid];
	}
};