Median of two sorted arrays

median_sorted.py

"""
  Merged to sorted array O(M + N) then find median O(1)
  Space: O(M + N) for temporary array
"""
def merge(first: List[int], second: List[int]) -> List[int]:
    M = len(first)
    N = len(second)
    i = j = 0
    result = []
    while i < M and j < N:
        if first[i] < second[j]:
            result.append(first[i])
            i += 1
        else:
            result.append(second[j])
            j += 1
    while i < M
        result.append(first[i])
        i += 1
    while j < N:
        result.append(second[j])
        j += 1
    return result

def median_merged(first: List[int], second: List[int]) -> float:
    merged = self.merge(first, second)
    MN = len(merged)
    mid = MN // 2
    if MN % 2 == 0:
        return (merged[mid - 1] + merged[mid]) / 2
    else:
        return merged[mid]
      
"""
  M = len(first)
  N = len(second)
  
  Binary search O(log(min(M, N))) since we search on smaller list
  Space: O(1)
  
  Median: Dividing a set into two equal length subsets, that one subset is always greater than the other.
  
  make first array to smaller size:
  Try to find partition point so that
    nums1[left of partion] <= nums2[right of partion]
    nums2[left of partion] <= nums1[right of partion]
  when we find this those will be our median since median is an partition that split array into two part that have same properties
 
  first_partition + second_partition =  M - first_partition + N - second_partition
    first_partition + second_partition = total - (first_partition + second_partition)
      second_partition = total / 2 - first_partition
"""

def median_partition(first: List[int], second: List[int]) -> float:
    M = len(first)
    N = len(second)
    MN = M + N
    if M > N:   # Make first array smaller
        M, N = N, M
        first, second = second, first

    MIN = float('-inf')
    MAX = float('inf')

    low = 0
    high = M
    while low <= high:
        first_partition = low + (high - low) // 2
        second_partition = (MN + 1) // 2 - first_partition

        first_left = first[first_partition - 1] if first_partition > 0 else MIN
        first_right = first[first_partition] if first_partition < M else MAX
        second_left = second[second_partition - 1] if second_partition > 0 else MIN
        second_right = second[second_partition] if second_partition < N else MAX

        if first_left <= second_right and second_left <= first_right:
            if MN % 2 == 0:
                return (max(first_left, second_left) + min(first_right, second_right)) / 2
            else:
                return max(first_left, second_left)
        elif first_left > second_right:
            high = first_partition - 1
        else:
            low = first_partition + 1

    raise Exception('Why are we here?')