Median of Two Sorted Arrays

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

思路：
（1）时间复杂度O（log(m+n)）,联想到递归法;
（2）问题形式化为：查找两个数组的第K大小的数findKth(A, m, B, n, topK);
（3）边界条件：凡是出现了加、减的地方都要考虑数组的上下界;
（4）两个数组大小不一样，计算机只解决一次就行，不用分开考虑。在函数头部加上调整数组顺序即可。

class Solution {
public:
    double findKth(int A[], int m, int B[], int n, int topK) {
      // always assume that m is equal or less than n
      if (m > n) {
	return findKth(B, n, A, m, topK);
      }

      if(m == 0) {
	return B[topK - 1];
      }

      if (topK == 1) {
	return min(A[0], B[0]);
      }
 
      // divide topK into two parts
      int pa = min(topK/2, m);
      int pb = topK - pa;

      if (A[pa-1] < B[pb-1]){
	return findKth(A+pa, m-pa, B, n, topK - pa);
      } else if (A[pa-1] > B[pb-1]) {
	return findKth(A, m, B+pb, n-pb, topK - pb);
      } else {
	return A[pa-1];
      }
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
      if ((m+n)%2 == 1) {
	return findKth(A, m, B, n, (m+n)/2 + 1) * 1.0;
      } else {
	return (findKth(A, m, B, n, (m+n)/2) + 
		findKth(A, m, B, n, (m+n)/2 + 1)) * 1.0 / 2;
      }
    }
};