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

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 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

原题如上：

在看完官方讲解视频后，将代码及代码解析注释提炼出来，如下：

package t4;public class zhongweishu {public static void main(String[] args) {int[] num1 = {7,9,11};int[] num2 = {2,8,12};//将长度短的设为第一个数组if (num1.length > num2.length) {int[] temp = num1;num1 = num2;num2 = temp;}//确定数组之后，再求数组长度int l1 = num1.length;int l2 = num2.length;//分割线左边的元素个数等于右边或比右边多一int total_left = (l1 + l2 + 1) / 2;//i和j分别表示在数组1和数组2的分割线右边那个数的下标，那么下标数也是分割线左边数组的个数//所以应该分割线应该满足num1[i-1]<=num2[j] && num2[j-1]<=num1[i]int left = 0;//让左查找区间边界为0int right = l1;//让右查找区间边界为短数组的长度while (left < right) {//当 left>=right 时退出循环，求到极限的时候，分割线的位置就可以确定下来了int i = left + (right - left + 1) / 2;//left和right中间位置的下标（取中位数），加一防止i-1的下标越界int j = total_left - i;//剩下的就是j//当分割线不满足要求时if (num1[i-1] > num2[j]){//分割线太靠num1的右边了，分割线应该在i位置的左边//下一个找分割线的区间应该是[left,i-1]这个区间right = i - 1;//更改右边界}else {//搜素区间为上个区间取反，[i,right]left = i;//更新左边界}}//循环过后重新定义i和jint i = left;int j = total_left - i;//分割线周围的四个元素可以确定下来了//为防止下标越界，要做出一些调整int n1_l_x = i == 0 ? Integer.MIN_VALUE : num1[i-1];int n1_r_n = i == l1 ? Integer.MAX_VALUE : num1[i];int n2_l_x = j == 0 ? Integer.MIN_VALUE : num2[j - 1];int n2_r_n = j == l2 ? Integer.MAX_VALUE : num2[j];if ((l1 + l2)%2 == 1) {//奇数个int mid = Math.max(n1_l_x, n2_l_x);System.out.println("中位数为：" + mid);}else {//偶数个double mid = (double) (Math.max(n1_l_x, n2_l_x)+Math.min(n1_r_n,n2_r_n)) /2;//注意强制转换System.out.println("中位数为：" + mid);}}
}

运行结果如下：