给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。

解法一：暴力合并排序

将两个数组合并成一个有序数组，然后找到其中位数即可。时间复杂度为 O(m+n)，不符合要求。

解法二：二分查找

可以考虑在数组中找到中位数，可以将问题转化为在两个有序数组中各自找到一个位置，使得这两个位置左边的所有数的数量之和等于总数的一半。为了保证时间复杂度为 O(log(m+n))，可以使用二分查找。

具体思路如下：

假设两个数组分别为 nums1 和 nums2，总长度为 len，中位数位置为 mid = (len+1)/2。
对 nums1 进行二分查找，找到一个位置 i，使得 nums1[i-1]<=nums2[mid-i] 且 nums2[mid-i-1]<=nums1[i]，这里需要注意的是，如果 i=0 或 i=m，则 nums1[i-1] 或 nums1[i] 不存在，可以用 -INF 或 INF 来替代。
如果 mid 为奇数，则中位数为 min(nums1[i], nums2[mid-i])。
如果 mid 为偶数，则中位数为 (max(nums1[i-1], nums2[mid-i-1])+min(nums1[i], nums2[mid-i]))/2。

时间复杂度为 O(log(min(m,n)))。

代码如下：

相关问题

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

可以使用Arrays.sort()方法来排序数组，然后使用Math.max()和Math.min()方法来比较两个数组中的最大值和最小值。之后使用if语句来判断两个数组的大小，并计算中位数（如果两个数组的总大小是偶数，那么取出两个数组的中间数字的均值作为中位数；如果两个数组的总大小是奇数，那么取出两个数组的中间数字作为中位数）。

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n))

方法一：归并排序

将两个有序数组合并成一个有序数组，然后找到中位数即可。

时间复杂度：O(m+n)

方法二：二分查找

假设数组 A 和数组 B 的长度分别为 m 和 n，中位数为第 k 小的数。那么我们需要找到一个位置 i，使得 A 数组中恰好有 i 个数小于 B 数组中的第 k-i 个数。此时，A 数组中前 i 个数和 B 数组中前 k-i 个数的联合就是数组 A 和数组 B 中前 k 个最小的数。因为 A 和 B 数组都是有序的，所以可以使用二分查找定位 i 的位置。

时间复杂度：O(log(min(m,n)))

具体实现见代码：