class Solution:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        len1 = len(nums1)
        len2 = len(nums2)
        # when total length is odd, the median is the middle
        if (len1 + len2) % 2 != 0:
            return self.get_kth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) // 2)
        else:
            # when total length is even, the median is the average of the middle 2
            middle1 = self.get_kth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) // 2)
            middle2 = self.get_kth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) // 2 - 1)
            return (middle1 + middle2) / 2

    def get_kth(self, nums1, nums2, start1, end1, start2, end2, k):
        if start1 > end1:
            return nums2[k - start1]
        if start2 > end2:
            return nums1[k - start2]

        middle1 = (start1 + end1) // 2
        middle2 = (start2 + end2) // 2
        middle1_value = nums1[middle1]
        middle2_value = nums2[middle2]

        # if sum of two median's indicies is smaller than k
        if (middle1 + middle2) < k:
            # if nums1 median value bigger than nums2, then nums2's first half will always be positioned before nums1's
            # median, so k would never be in num2's first half
            if middle1_value > middle2_value:
                return self.get_kth(nums1, nums2, start1, end1, middle2 + 1, end2, k)
            else:
                return self.get_kth(nums1, nums2, middle1 + 1, end1, start2, end2, k)
        # if sum of two median's indicies is bigger than k
        else:
            # if nums1 median value bigger than nums2, then nums2's first half would be merged b4 nums1's first half,
            # thus k always come before nums1's median, then nums1's second half would never include k
            if middle1_value > middle2_value:
                return self.get_kth(nums1, nums2, start1, middle1 - 1, start2, end2, k)
            else:
                return self.get_kth(nums1, nums2, start1, end1, start2, middle2 - 1, k)


class Solution3:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        total = len(nums1) + len(nums2)
        half = total // 2 - 2  # list index starts at 0
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        l, r = 0, len(nums1) - 1

        while True:
            middle1 = (l + r) // 2
            middle2 = half - middle1
            nums1_left = nums1[middle1] if middle1 >= 0 else float("-infinity")
            nums1_right = nums1[middle1 + 1] if middle1 + 1 < len(nums1) else float("infinity")
            nums2_left = nums2[middle2] if middle2 >= 0 else float("-infinity")
            nums2_right = nums2[middle2 + 1] if middle2 + 1 < len(nums2) else float("infinity")
            if nums1_left <= nums2_right and nums2_left <= nums1_right:
                if total % 2 == 1:
                    return min(nums2_right, nums1_right)
                if total % 2 == 0:
                    return (min(nums2_right, nums1_right) + max(nums1_left, nums2_left)) / 2
            elif nums1_left > nums2_right:
                r = middle1 - 1
            elif nums2_left > nums1_right:
                l = middle1 + 1


class Solution4:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        total = len(nums1) + len(nums2)
        half = (total + 1) // 2 - 2  # list index starts at 0
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        l, r = 0, len(nums1) - 1

        while True:
            middle1 = (l + r) // 2
            middle2 = half - middle1
            nums1_left = nums1[middle1] if middle1 >= 0 else float("-infinity")
            nums1_right = nums1[middle1 + 1] if middle1 + 1 < len(nums1) else float("infinity")
            nums2_left = nums2[middle2] if middle2 >= 0 else float("-infinity")
            nums2_right = nums2[middle2 + 1] if middle2 + 1 < len(nums2) else float("infinity")
            if nums1_left <= nums2_right and nums2_left <= nums1_right:
                if total % 2 == 1:
                    return max(nums1_left, nums2_left)
                if total % 2 == 0:
                    return (min(nums2_right, nums1_right) + max(nums1_left, nums2_left)) / 2
            elif nums1_left > nums2_right:
                r = middle1 - 1
            elif nums2_left > nums1_right:
                l = middle1 + 1


print(Solution().findMedianSortedArrays([0, 0], [0, 0]))
