4.寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
           

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
           

二分查找

直接求中位数可能不好想到，那么我们换个思路.假设有下面两个数组 A 和 B，A数组的长度是4，B数组的长度是8。

意境级讲解二分查找算法、python

如上图，因为A+B的总长度是12，是偶数，所以求中位数的话，需要找到第6小、第7小的元素，找到这两个元素后，相加再 / 2 就可以了。

这里是偶数长度的情况，如果是两个数组长度相加后是奇数也是类似的，比如总长度是 13 ，那就需要找第7小的元素。

所以，这题可以转化为，如何找到第k小的元素。

• 如果总长度N是偶数，则需要找到两个数组中第

  N / 2

  小的元素、第

  N / 2 + 1

  小的元素
• 如果总长度N是奇数，则需要找到两个数组中第

  N / 2 + 1

  小的元素

题目限制了时间复杂度，所以这里找第k小的过程，肯定也是二分的方式。

假设两个有序数组分别是 A \mathrm{A} A​ 和 B \mathrm{B} B​ 。要找到第 k k k​ 个元素，我们可以比较 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1]​ 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1]​, 其 中 / / /​ 表示整数除法。由于 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1]​ 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1]​ 的前面分别有 A [ 0 … k / 2 − 2 ] \mathrm{A}[0 \ldots k / 2-2] A[0…k/2−2]​ 和 B [ 0.. k / 2 − 2 ] \mathrm{B}[0 . . k / 2-2] B[0..k/2−2]​, 即 k / 2 − 1 k / 2-1 k/2−1​ 个元素, 对于 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1]​ 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1]​ 中的较小值，最多只会有 ( k / 2 − 1 ) + ( k / 2 − (k / 2-1)+(k / 2- (k/2−1)+(k/2−​ 1) ≤ k − 2 \leq k-2 ≤k−2​ 个元素比它小，那么它就不能是第 k k k​ 小的数了。

因此我们可以归纳出三种情况：

• 如果 A [ k / 2 − 1 ] < B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]<\mathrm{B}[k / 2-1] A[k/2−1]<B[k/2−1], 则比 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 小的数最多只有 A \mathrm{A} A 的前 k / 2 − 1 k / 2-1 k/2−1 个数和 B \mathrm{B} B 的 前 k / 2 − 1 k / 2-1 k/2−1 个数, 即比 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 小的数最多只有 k − 2 k-2 k−2 个， 因此 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 不可能是第 k k k 个 数, A [ 0 ] \mathrm{A}[0] A[0] 到 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 也都不可能是第 k k k 个数, 可以全部排除。
• 如果 A [ k / 2 − 1 ] > B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]>\mathrm{B}[k / 2-1] A[k/2−1]>B[k/2−1], 则可以排除 B [ 0 ] \mathrm{B}[0] B[0] 到 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 。
• 如果 A [ k / 2 − 1 ] = B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]=\mathrm{B}[k / 2-1] A[k/2−1]=B[k/2−1], 则可以归入第一种情况处理。

可以看到，比较 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 之后，可以排除 k / 2 k / 2 k/2 个不可能是第 k k k 小的数， 查找范围缩 小了一半。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减 少 k k k 的值，这是因为我们排除的数都不大于第 k k k 小的数。有以下三种情况需要特殊处理：

• 如果 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 或者 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这 种情况下，我们必须根据排除数的个数减少 k k k 的值，而不能直接将 k k k 减去 k / 2 k / 2 k/2 。
• 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k k k 小的元素。
• 如果 k = 1 k=1 k=1, 我们只要返回两个数组首元素的最小值即可。

因为数组A、数组B都是有序的，所以我们需要利用这个有用的特性，每次缩小查找范围:第一次找 k 小、第二次就是找 k/2 小、然后是 k/4小，直到 k 等于1时。

还是以上面的数组为例，A数组为

[1,2,4,9]

，B数组是

[1,2,3,4,5,6,7,8]

. 我们需要找第6、第7小的元素，假设我们先找第6小的元素，也就是k = 6。要找到第 k k k 个元素，我们可以比较 A [ k / 2 − 1 ] \text{A}[k/2-1] A[k/2−1]和 B [ k / 2 − 1 ] \text{B}[k/2-1] B[k/2−1]

我们首先比较 A数组中第3个元素，B数组中第3个元素，也就是

A[k/2-1]

和

B[k/2-1]

，如下图：

由于A[k/2-1] > B[k/2-1]，这时候我们就可以忽略掉一些元素了。

上图中 A数组中的4，它前面有2个元素，也就是

k/2-1

个元素，B数组的3，它前面也有2个元素，也就是

k/2-1

个元素，一共有

k-2

个元素

假设 B数组的

3

，也就是B[k/2-1] 比这

k-2

个元素都大。这样的话，我们就可以排除一些元素了，

既然B[k/2-1]都不是第k小的元素，那么 B[k/2-1]前面的那些更不是了，于是我们将B[0]、B[1]、B[2]。。。B[k/2-1]这些元素全部忽略掉。

当我们忽略掉 B数组中的元素后， k也要跟着减小，

k- k//2=3

。这个解法的整体求解过程，就是不断缩小数组的规模，同时把k也跟着缩小。如下图

这次 k=3，

k//2-1=0

,所以A[k/2-1]对应的就是A[0],B[k/2-1]对应是B[3]，因为我们之前忽略掉了 B数组中的前3个元素，所以B数组的第1个元素是从下标3开始的。 如下图橙色为

k//2-1

：

经过这次比较后，

A[k/2-1] < B[k/2-1]

，所以忽略掉

A[0]

，然后将 k 变成

k- k//2=2

。

k此时等于2，

k//2-1=0

,于是

A[k/2-1]

对应的是

A[1]

，因为刚才已经忽略掉

A[0]

了,

B[k/2-1]

对应的是

B[3]

,如下图：

经过这次比较后，

A[k/2-1] < B[k/2-1]

，所以忽略掉

A[1]

，然后将 k 变成

k- k//2=1

。

当k==1时，返回A数组中第一个元素 和 B数组中第一个元素的较小者。

此时A数组中的第1个元素是A[2]，B数组中第1个元素是B[3]，即求

min(A[2],B[3])

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        def getKthElement(k):
            """
            - 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
            - 这里的 "/" 表示整除
            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
            - 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
            - 这样 pivot 本身最大也只能是第 k-1 小的元素
            - 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
            - 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
            - 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小）,因此需要修改 k 的值,减去删除的数的个数
            """
            index1, index2 = 0, 0
            while True:
                # 特殊情况
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                if k == 1:
                    return min(nums1[index1], nums2[index2])
                
                # 正常情况,index1,index2作为起始点,newindex1,newindex2作为比较点 在不停的更新
                newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 第一种特殊情况,发生越界,记录需要比较的位置
                newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 第一种特殊情况,发生越界,记录需要比较的位置
                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 获取两个需要比较的数
                if pivot1 <= pivot2:  # <=将两种情况合并
                    k -= newIndex1 - index1 + 1  # 两者相减后+1,这才是真正减去的长度
                    index1 = newIndex1 + 1  # 连同比较位置也一同删去了,所以新的开始是 比较位置 的后一位
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
        

        totalLength = m + n
        if totalLength % 2 == 1:  # 可以将两种情况合并,奇数会求两次同样的k
            return getKthElement((totalLength + 1) // 2)
        else:
            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
           

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k//2-1] 和 pivot2 = nums2[k//2-1] 进行比较
            - 这里的 "//" 表示整除
            nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
            nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
        """
        total = len(nums1) + len(nums2)
        # 如果A数组长度+B数组长度total是奇数，则找total/2+1小的元素
        # 即为中位数
        if total % 2 == 1:
            midIndex = total // 2 + 1
            res = self.getKthElement(nums1, nums2, midIndex)
            return float(res)
        # 否则，找total/2，total/2+1这两个元素    
        else:
            midIndex_1 = total // 2
            midIndex_2 = total // 2 + 1
            a = self.getKthElement(nums1, nums2, midIndex_1)
            b = self.getKthElement(nums1, nums2, midIndex_2)
            return (a + b) / 2.0

    def getKthElement(self,nums1, nums2, k):
        len1 = len(nums1)
        len2 = len(nums2)
        index1 = 0
        index2 = 0
        while True:
            # 边界情况，当index1越界时，直接返回nums2的第k小元素
            if index1 == len1:
                return nums2[index2 + k -1]
            # 边界情况，当index2越界时，直接返回nums1的第k小元素
            if index2 == len2:
                return nums1[index1 + k - 1]
            # 边界情况，k等于1时，返回nums1第一个元素和nums2第一个元素较小者
            if k == 1:
                return min(nums1[index1], nums2[index2])
            new_index1 = min(index1 + k // 2- 1 , len1- 1 ) 
            new_index2 = min(index2 + k // 2 - 1, len2 - 1)
            pivot1 = nums1[new_index1]
            pivot2 = nums2[new_index2]
            # 比较nums1[k/2-1]和nums2[k/2-1]
            # 如果nums1的小，则忽略掉nums1[0] - nums1[k/2-1]这些元素
            # 再更新 k，k 要减去忽略掉的那些元素，index1也要更新，待下轮使用
            if pivot1 <= pivot2:
                k -= (new_index1 - index1 + 1)
                index1 = new_index1 + 1
            # 如果nums2的小，则忽略掉nums2[0] - nums2[k/2-1]这些元素
            # 再更新 k，k 要减去忽略掉的那些元素，index2也要更新，待下轮使用
            else:
                k -= (new_index2 - index2 + 1)
                index2 = new_index2 + 1
           

复杂度分析

• 时间复杂度： O ( log ⁡ ( m + n ) ) O(\log (m+n)) O(log(m+n)), 其中 m m m 和 n n n 分别是数组 n u m s 1 nums_{1} nums1​ 和 n u m s 2 n u m s_{2} nums2​ 的长度。初始时有 k = ( m + n ) / 2 k=(m+n) / 2 k=(m+n)/2 或 k = ( m + n ) / 2 + 1 k=(m+n) / 2+1 k=(m+n)/2+1, 每一轮循环可以将查找范围减少一半， 因此时间复杂度 是 O ( log ⁡ ( m + n ) ) O(\log (m+n)) O(log(m+n)) 。
• 空间复杂度：O(1)。

划分数组

为了使用划分的方法解决这个问题，需要理解「中位数的作用是什么」。在统计中，中位数被用来：

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

如果理解了中位数的划分作用，就很接近答案了。

首先，在任意位置 i i i 将 A \text{A} A 划分成两个部分：

left_A            |          right_A
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
           

由于 A \mathrm{A} A 中有 m m m 个元素， 所以有 m + 1 m+1 m+1 种划分的方法 ( i ∈ [ 0 , m ] ) (i \in[0, m]) (i∈[0,m]) 。

l e n ( l e f t A ) = i , l e n ( r i g h t A ) = m − i len(left_A)=i,len(right_A)=m−i len(leftA​)=i,len(rightA​)=m−i.

注意：当 i = 0 i=0 i=0 时，left_A 为空集， 而当 i = m i=m i=m 时, right_A 为空集。

采用同样的方式，在任意位置 j j j 将 B \text{B} B 划分成两个部分：

left_B            |          right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
           

将 left_A 和 left_B 放入一个集合，并将 right_A 和 right_B放入另一个集合。 再把这两个新的集合 分别命名为left_part 和 right_part:

left_part          |         right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
           

当 A \mathrm{A} A 和 B \mathrm{B} B​ 的总长度是偶数时，如果可以确认：

• len(left_part) = = =​ len(right_part) :

  i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i

• max(left_part ) ≤ min ⁡ ( ) \leq \min ( )≤min( right_part ) ) )

  max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））

• 那么， { A , B } \{\mathrm{A}, \mathrm{B}\} {A,B}​ 中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等 于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值:

 median  = max ⁡ (  left_part  ) + min ⁡ (  right_part  ) 2 （ m a x ( A [ i − 1 ] , B [ j − 1 ] ） + m i n ( A [ i ] , B [ j ] ） ） / 2 \text { median }=\frac{\max (\text { left\_part })+\min (\text { right\_part })}{2}\\ （max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2  median =2max( left_part )+min( right_part )​（max(A[i−1],B[j−1]）+min(A[i],B[j]））/2

当 A \mathrm{A} A 和 B 的总长度是奇数时，如果可以确认：

• len(left_part ) = )= )= len(right_part) + 1 +1 +1​

  i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i

• max(left_part ) ≤ min ⁡ ( ) \leq \min ( )≤min( right_part ) ) )
• 那么, { A , B } \{\mathrm{A}, \mathrm{B}\} {A,B} 中的所有元素已经被划分为两个部分，前一部分比后一部分多一个元素, 且前一部分 中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值:

 median  = max ⁡ (  left_part  ) m a x ( A [ i − 1 ] , B [ j − 1 ] ） \text { median }=\max (\text { left\_part })\\ max ( A [ i - 1 ] , B [ j - 1 ]）  median =max( left_part )max(A[i−1],B[j−1]）

第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。

i + j = m + n + 1 2 i+j=\frac{m+n+1}{2} i+j=2m+n+1​

第二个条件对于 总长度是偶数和奇数的情况是一样的。

要确保这两个条件，只需要保证：

• 0 ≤ i ≤ m , 0 ≤ j ≤ n 0 \leq i \leq m, 0 \leq j \leq n 0≤i≤m,0≤j≤n​ 。 如果我们规定 A \mathrm{A} A​ 的长度小于等于 B \mathrm{B} B​ 的长度， 即 m ≤ n ∘ m \leq n_{\circ} m≤n∘​​ 这样对于任意的 i ∈ [ 0 , m ] i \in[0, m] i∈[0,m]​, 都有 j = m + n + 1 2 − i ∈ [ 0 , n ] j=\frac{m+n+1}{2}-i \in[0, n] j=2m+n+1​−i∈[0,n]​, 那么我们在 [ 0 , m ] [0, m] [0,m]​ 的范围内枚举 i i i​ 并得到 j j j​, 就 不需要额外的性质了。
• 如果 m > n m>n m>n, 那么得出的 j j j 有可能是负数。那么我们只要交换 A \mathrm{A} A​ 和 B 即可。

为了保证

max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））

,因为 A 数组和 B 数组是有序的，所以 B [ j − 1 ] ≤ A [ i ] \mathrm{B}[j-1] \leq \mathrm{A}[i] B[j−1]≤A[i] 以及 A [ i − 1 ] ≤ B [ j ] , \mathrm{A}[i-1] \leq \mathrm{B}[j], \quad A[i−1]≤B[j], 即前一部分的最大值小于等于后一部分的最小值。

为了简化分析，假设 A [ i − 1 ] , B [ j − 1 ] , A [ i ] , B [ j ] \mathrm{A}[i-1], \mathrm{B}[j-1], \mathrm{A}[i], \mathrm{B}[j] A[i−1],B[j−1],A[i],B[j] 总是存在。对于 i = 0 , i = m , j = 0 、 j = n i=0, i=m, j=0 、 j=n i=0,i=m,j=0、j=n 这样 的临界条件，我们只需要规定 A [ − 1 ] = B [ − 1 ] = − ∞ , A [ m ] = B [ n ] = ∞ \mathrm{A}[-1]=\mathrm{B}[-1]=-\infty, A[m]=\mathrm{B}[n]=\infty A[−1]=B[−1]=−∞,A[m]=B[n]=∞​ 即可。这也是比较直观 的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响; 当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。

所以我们需要做的是：

在 [ 0 , m ] [0, m] [0,m] 中找到 i i i, 使得：

B [ j − 1 ] ≤ A [ i ] \mathrm{B}[j-1] \leq \mathrm{A}[i] B[j−1]≤A[i] 且 A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j], 其中 j = m + n + 1 2 − i j=\frac{m+n+1}{2}-i j=2m+n+1​−i

我们证明它等价于：

在 [ 0 , m ] [0, m] [0,m] 中找到最大的 i i i, 使得:

A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j], 其中 j = m + n + 1 2 − i j=\frac{m+n+1}{2}-i j=2m+n+1​−i​​​​

这是因为:

• 当 i i i 从 0 ∼ m 0 \sim m 0∼m 递增时, A [ i − 1 ] \mathrm{A}[i-1] A[i−1] 递增, B [ j ] \mathrm{B}[j] B[j] 递减，所以一定存在一个最大的 i i i 满足 A [ i − 1 ] ≤ \mathrm{A}[i-1] \leq A[i−1]≤ B [ j ] \mathrm{B}[j] B[j]
• 如果 i i i 是最大的， 那么说明 i + 1 i+1 i+1 不满足。将 i + 1 i+1 i+1 带入可以得到 A [ i ] > B [ j − 1 ] \mathrm{A}[i]>\mathrm{B}[j-1] A[i]>B[j−1], 也就是 B [ j − 1 ] < A [ i ] \mathrm{B}[j-1]<\mathrm{A}[i] B[j−1]<A[i], 就和我们进行等价变换前 i i i 的性质一致了（甚至还要更强）。

因此我们可以对 i i i 在 [ 0 , m ] [0, m] [0,m] 的区间上进行二分搜索，找到最大的满足 A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j] 的 i i i 值，就得 到了划分的方法。此时，划分前一部分元素中的最大值，以及划分后一部分元素中的最小值，才可 能作为就是这两个数组的中位数。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)

        infinty = 2**40
        m, n = len(nums1), len(nums2)
        left, right = 0, m
        # median1：前一部分的最大值
        # median2：后一部分的最小值
        median1, median2 = 0, 0

        while left <= right:
            # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i

            # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            # 当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响
            nums_im1 = (-infinty if i ==0 else  nums1[i - 1])
            nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
            # 当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响
            nums_i = (infinty if i == m else nums1[i])
            nums_j = (infinty if j == n else nums2[j])

            if nums_im1 < nums_j:
                 median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
                 left = i + 1
            else:
                right = i - 1

        return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

           

• 时间复杂度： O ( log ⁡ min ⁡ ( m , n ) ) ) O(\log \min (m, n))) O(logmin(m,n))), 其中 m m m 和 n n n 分别是数组 n u m s 1 n u m s_{1} nums1​ 和 n u m s 2 n u m s_{2} nums2​ 的长度。查找的区 间是 [ 0 , m ] [0, m] [0,m], 而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 log ⁡ m \log m logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为 O ( log ⁡ m ) O(\log m) O(logm) 。 由于我们可 能需要交换 n u m s 1 n u m s_{1} nums1​ 和 n u m s 2 n u m s_{2} nums2​ 使得 m ≤ n m \leq n m≤n, 因此时间复杂度是 O ( log ⁡ min ⁡ ( m , n ) ) ) \left.O(\log \min (m, n))\right) O(logmin(m,n))) 。
• 空间复杂度：O(1)。

参考

力扣（LeetCode） (leetcode-cn.com)