class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        if len(nums1) == 0:
            return self.median(nums2)
        elif len(nums2) == 0:
            return self.median(nums1)

        l = len(nums2) + len(nums1)

        even = l % 2 == 0

        if even:
            m1 = self.findMed(nums1, nums2, True)
            m2 = self.findMed(nums1, nums2, False)
            return (m1 + m2)/2
        else:
            return self.findMed(nums1, nums2, True)


    def median(self, num):
        if len(num) % 2 == 0:
            return (num[(len(num) - 1 ) //2] + num[len(num) //2]) /2
        else:
            return num[(len(num)) //2]

    def findMed(self, nums1, nums2, first):
        # print ( 'in findMed', nums1, nums2, first)
        ma = max(nums1[len(nums1) - 1], nums2[len(nums2) - 1])
        mi = min(nums1[0], nums2[0])

        r = ma
        l = mi

        mid = (r + l)//2
        while l <= r:

            cmp = self.cmpMedian(nums1, nums2, mid, first)
            # print('here', l, r, 'mid ', mid, 'cmp ', cmp)
            if cmp == 0:
                return mid
            elif cmp > 0:
                r = mid - 1
            else:
                l = mid + 1

    def cmpMedian(self, num1, num2, k ,first):
        # print ( 'in cmpMedian', num1, num2, k, first)
        l = len(num2) + len(num1)
        even = l % 2 == 0

        if not even:
            if  self.less(num1, num2, k) > l//2:
                # print ('less 1,', num1, num2, k, self.less(num1, num2, k))
                return 1
            if  self.less(num1, num2, k + 1) < l//2:
                # print ('less -1,', num1, num2, k + 1, self.less(num1, num2, k + 1))
                return -1
            else:
                # print('less returning 0')
                return 0

        else:
            if first:
                if  self.less(num1, num2, k) > l//2:
                    return 1
                if  self.less(num1, num2, k + 1) < l//2:
                    return -1
                else:
                    return 0
            else:
                if  self.less(num1, num2, k) > (l + 1)//2:
                    return 1
                if  self.less(num1, num2, k + 1) < (l+ 1)//2:
                    return -1
                else:
                    return 0


    def less(self, num1, num2, k):
        # print ( 'in less', num1, num2, k)
        l = 0
        r = len(num1) - 1
        res = -1
        while l <= r:
            mid = (l + r)//2
            if num1[mid] == k:
                res = mid
                break
            if num1[mid] < k:
                l = mid + 1
            else:
                r = mid -1
        if res == -1: res = l

        l = 0
        r = len(num2) - 1
        while l <= r:
            mid = (l + r)//2
            if num2[mid] == k:
                return res + mid
            if num2[mid] < k:
                l = mid + 1
            else:
                r = mid -1

        return res + l