题目：求两个升序数组合并后的中间值，如，［1，3，4］［2］中间值 2＋3/2=2.5
以下复杂度 logn 解法是网上找到的，感觉讲的不是很好理解，这里举个栗子说明下，也不知道发哪个板块，就发这里了

class Solution(object):
    # 这是在网上找到的一个算法，非常有效,就是将问题转化为求第k小的那个数
    # 假设数组A,B,长度分别为la,lb,如果la与lb都大于k/2,
    # a0, a1,a2,...,a(k/2-1),...,a(la)
    # b0, b1,b2,...,b(k/2-1),...,b(lb)
    # 如果a(k/2-1) <= b(k/2-1),则合并后a0到a(k/2-1)排在b(k/2-1)后,第k小的数不可能属于A(0,k/2-1)，这部分数据抛弃掉
    # 为了好理解 看一个简单的栗子
    # A 1,2,3,5,7,9,10,12,18,20,21,22,23,24 ,la = 14个数
    # B 4,6,8,11,13                         ,lb =  5个数
    # 由于la+lb=19,也就是求第10小的数（中间数），
    # ******A(4) = 7 < B(4) = 13,这样把A(0-4)的5个元素删除了
    # 等于在剩下元素求第(10-5)=5小的数,这样问题就出现同上一步操作了(递归)
    # A 9,10,12,18,20,21,22,23,24
    # B 4, 6, 8,11,13
    # 由于 5%2 != 0，这里取A前三个元素(9,10,12),B前两个B(4,6),当然也可以取(9,10)与(4,6,8)
    # ******A(2) = 12 > B(1)=6,这样把B(0-1)的两个元素删除了
    # 等于在剩下元素求第(10-5-2)=3小的数，这样问题就出现同上一步操作了(递归)
    # A 9,10,12,18,20,21,22,23,24
    # B 8,11,13
    # 由于 3%2 != 0 这一次A取一个元素 9，B前两个元素(8,11),也可以取(9,10)与(8)
    # ******A(0) = 9 < B(1) = 11,这样把A(0) = 9删除了
    # 等于在剩下元素求第(10-5-2-1)=2小的数，这样问题就出现同上一步操作了(递归)
    # A 10,12,18,20,21,22,23,24
    # B 8,11,13
    # 2%2=0,A(10),B(8)
    # ******A(0)=10 > B(0) = 8,这样把B(0)=8删除了
    # 等于在剩下元素求第(10-5-2-1-1)=1小的数，这样问题就出现同上一步操作(递归)
    # A 10,12,18,20,21,22,23,24
    # B 11,13
    # 第一小(递归终止)，只要比较A(0) = 10 < B(0) = 11,A(0) = 10就是第一小了，也是整个数据的第十小
    # 1,2,3,(B)4,5,(B)6,7(B)8,9,***10***,B(11),12,(B)13,18,20,21,22,23,24
    #***********************************************
    # nums1 第一个数组
    # nums1 第二个数组
    # k，第k小的数
    def find(self, nums1, nums2, k):
        l1, l2= len(nums1), len(nums2)
        # k不能大于l1+l2
        if k > l1+l2 or l1+l2==0 or k == 0:
            return False
        # 始终l1 > l2
        if l1 < l2:
            return self.find(nums2, nums1,k)
        if k == 1:
            if l2 == 0:
                return nums1[0]
            else:
                return min(nums1[0], nums2[0])
        if l2 == 0:
            return nums1[k-1]
        # 这里如果l1,l2,k/2有几种情况
        # 1: k/2有可能小于l2 
        r = min(k/2, l2)
        if nums1[k-r-1] < nums2[r-1]:
            # 删除nums1中的k-r个元素,在剩余找出第r小的数
            return self.find(nums1[(k-r):], nums2,r)
        else:
            # 删除nums2中r个元素,在剩余找出第k-r小的数
            return self.find(nums1, nums2[r:], k-r)

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        l1, l2 = len(nums1), len(nums2)
        if (l1+l2)%2 != 0:
            return self.find(nums1, nums2, (l1+l2)/2+1)
        else:
            lRe1 = self.find(nums1, nums2, (l1+l2)/2)
            lRe2 = self.find(nums1, nums2, (l1+l2)/2+1)
            return (lRe1 + lRe2)/2.0