在两个长度相等的排序数组中找到上中位数

问题简述

给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，为第n/2个数

在两个长度相等的排序数组中找到上中位数_牛客题霸_牛客网

思路

• 相比 LeetCode 版，本题不需要处理奇数情况，同时在 i==0/N 时的判断更简单；

  寻找两个正序数组的中位数 - LeetCode

• 二分目标：找到最大的 i，使 A[i - 1] <= B[j]，其中 i + j == N；

• 思路简述：将 A, B 分别分成如下两组，且保证 max(A_i-1, B_j-1) <= min(A_i, B_j)，根据中位数性质，目标值即 max(A_i-1, B_j-1)；

  • 可证，上述条件等价于找到最大的 i，使 A[i - 1] <= B[j]（证明详见参考链接）

  寻找两个有序数组的中位数 - 力扣官方题解

      A_0, .., A_i-1 | A_i, .., A_N-1
      B_0, .., B_j-1 | B_j, .., B_N-1
  其中
      i + j == N

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# find median in two sorted array
# @param arr1 int整型一维数组 the array1
# @param arr2 int整型一维数组 the array2
# @return int整型
#
class Solution:
    def findMedianinTwoSortedAray(self , arr1: List[int], arr2: List[int]) -> int:
        # write code here
        if arr1[-1] <= arr2[0]: return arr1[-1]
        if arr2[-1] <= arr1[0]: return arr2[-1]
        
        N = len(arr1)
        l, r = 0, N  # [l, r) 左闭右开区间，注意始终保证这个条件
        
        while l < r:
            # 这里的 i、j 是数量的概念，而不是下标
            i = (l + r + 1) // 2  # A 中的前 i 个数
            j = N - i  # B 中的前 j 个数
            
            if arr1[i - 1] <= arr2[j]:
                l = i  # [l, i-1] 区间满足要求，下一轮在 [i, r) 中继续找更大的，所以使 l = i
            else:
                r = i - 1  # [i-1, r) 区间不满足要求，下一轮从 [l, i-1) 继续找符合的，所以令 r = i - 1
        
        i = (l + r + 1) // 2
        j = N - i
        
        if i == 0:
            return arr2[-1]
        elif i == N:
            return arr1[-1]
        else:
            return max(arr1[i - 1], arr2[j - 1])