[LeetCode] 4. Median of Two Sorted Arrays

Problem : https://leetcode.com/problems/median-of-two-sorted-arrays/

A naive solution is firstly merge the 2 sorted arrays then calculate median value of the merged array.  Merging 2 sorted arrays takes O(m + n) time.  Calculating median value takes O(1) time. So the overall time complexity is O(m + n). It does not meet the requirement.  

Hence we need to use binary search to locate the median element.

Assume the merged array Merged's size = N.

Median value =  ( Merged[(N+1) // 2]  + Merged[(N+2)//2] ) // 2.0

So the solution is binary search the element (N+1) // 2 and (N+2) // 2

Time complexity: O(log(m + n))
Space complexity: O(1)

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        def findKth(i, j, k):
            """
            find the Kth number in the merged array.
            :type i: start index of nums1
            :type j: start index of nums2
            """
            while i < len(nums1) or j < len(nums2):
                if i >= len(nums1):
                    # all numbers in num1 are out of scope
                    return nums2[j + k - 1]
                
                if j >= len(nums2):
                    # all numbers in num2 are out of scope
                    return nums1[i + k - 1]
                
                if k == 1:
                    # return the smallest for the 1th number
                    return min(nums1[i], nums2[j])
            
                mid1 = 2**31 - 1  # maxmium int
                mid2 = 2**31 - 1
            
                if i + k // 2 - 1 < len(nums1):
                    mid1 = nums1[i + k // 2 - 1]
                
                if j + k // 2 - 1  < len(nums2):
                    mid2 = nums2[j + k // 2 - 1]
            
                if mid1 < mid2:
                    # remove k / 2 items of nums1 from scope
                    i = i + k // 2
                else:
                    # remove k / 2 items of nums2 from scope
                    j = j + k // 2
                
                k = k - k // 2
                
            
        left = (len(nums1) + len(nums2) + 1) // 2
        right = (len(nums1) + len(nums2) + 2) // 2
        
        return (findKth(0, 0, left) + findKth(0, 0, right)) / 2.0