4. Median of Two Sorted Arrays.md

4. Median of Two Sorted Arrays (Hard)

Algorithm: Binary Search based on constrains and conditions.

• constrai1: nums1 left + nums2 left = (len+1) / 2. there is one more on the left.
• use binary search to move the curser for nums1, and nums2 will move accrodingly.
• when l1_value > r2_value, move l1 curser to the left.
• when l2_value > r1_value, need to move l2 curser to the left by moving l1 curser to the right.
• when l1_value < r2_value and l2_value < r2_value, condition meet.
  • if odd total length, return max of l1_value and l2_value since ther is an extra 1 on the left.
  • if even total length, return average of max(l1_value, l2_value) and min(r1_value, r2_value).

'''
1 2 3| 4 5 7 
1 3| 4 5 6
'''
MIN_INT = -sys.maxsize - 1
MAX_INT = sys.maxsize
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len_1, len_2, len_all = len(nums1), len(nums2), len(nums1) + len(nums2)
        # do search on the smaller array.
        if len_2 < len_1:
            return self.findMedianSortedArrays(nums2, nums1)
        l_1, r_1 = 0, len_1

        while(l_1 <= r_1):
            cut_1 = (l_1 + r_1) // 2
            # there is one more element on the left side
            cut_2 = (len_all+1) // 2 - cut_1
            l1_value = MIN_INT if cut_1 == 0 else nums1[cut_1-1]
            l2_value = MIN_INT if cut_2 == 0 else nums2[cut_2-1]
            r1_value = MAX_INT if cut_1 == len_1  else nums1[cut_1]
            r2_value = MAX_INT if cut_2 == len_2 else nums2[cut_2]
            # nums1 left too large move left
            if l1_value > r2_value:
                # print('move left')
                r_1 = cut_1 - 1
            elif l2_value > r1_value:
                # print('move right')                
                l_1 = cut_1 + 1
            else:
                if len_all % 2 == 0:
                    return (max(l1_value, l2_value) + min(r1_value, r2_value)) / 2
                else:
                    return max(l1_value, l2_value)