code

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total_length = len(nums1) + len(nums2)
        if total_length % 2 == 1: # odd
            return self.findKth(nums1, nums2, total_length / 2 + 1)
        else:
            # even, pick two and average them
            smaller = self.findKth(nums1, nums2, total_length / 2)
            print "small: " + str(smaller)
            bigger = self.findKth(nums1, nums2, total_length / 2 + 1)
            print "bigger: " + str(bigger)
            return (smaller + bigger) / 2.0

    def findKth(self, nums1, nums2, k):
        print "-------"
        print nums1
        print nums2
        print k
        if len(nums1) == 0:
            return nums2[k-1]
        if len(nums2) == 0:
            return nums1[k-1]
        if k == 1:
            return min(nums1[0], nums2[0])

        if len(nums1) < k / 2:
            mid_1 = None
        else:
            mid_1 = nums1[k/2 - 1]

        if len(nums2) < k / 2:
            print "2 too short"
            mid_2 = None
        else:
            mid_2 = nums2[k/2 - 1]

        if mid_1 == None:
            print "not 1"
            return self.findKth(nums1, nums2[k/2:], k - k/2)
        if mid_2 == None:
            print "not 2"
            return self.findKth(nums1[k/2:], nums2, k - k/2)
        if mid_1 < mid_2:
            print "1 < 2"
            return self.findKth(nums1[k/2:], nums2[:k/2+1], k - k/2)
        elif mid_1 > mid_2:
            print "1 > 2"
            return self.findKth(nums1[:k/2+1], nums2[k/2:], k - k/2)
        else:
            if k % 2 == 0:
                return mid_1
            else:
                return min(nums1[k/2], nums2[k/2])

so = Solution()
nums1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22]
nums2 = [0,6]
re = so.findMedianSortedArrays(nums1, nums2)
print re