算法刷题 | 二分查找014.12 寻找两个正序数组的中位数

文章目录

• 3.确定两个有序数组的中位数
  • • 3.1题目内容
    • 3.2解决方式：采用暴力法（归并排序）
    • 3.3解决方式：运用二分查找法

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

3.1题目

已知存在两个正序排列（按升序排列）的数组 nums1 和 nums2，其元素数量分别为 m 和 n。请确定并返回这两个有序数组的 中位数 。

所设计的算法时间复杂度需满足 O(log (m+n)) 的要求。

• 示例一：

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

3.2解法：暴力（归并排序）

• 题目中所给的两个有序数组，可以通过合并的方式形成一个新的有序数组
  • 需要先确定合并后数组的长度是奇数还是偶数，从而计算出对应的中位数值
  • 归并排序所耗费的时间