第3关：寻找两个等长有序序列的中位数

[TOC]寻找两个等长有序序列的中位数
对于一个长度为n的有序序列（假设均为升序序列）a[0…n-1]，处于中间位置的元素称为a的中位数。
设计一个算法求给定的两个有序序列的中位数。
例如，若序列a=(11，13，15，17，19)，其中位数是15，若b=(2，4，6，8，20)，其中位数为6。两个等长有序序列的中位数是含它们所有元素的有序序列的中位数，例如a、b两个有序序列的中位数为11。

任务描述
本关任务：编写一个能计算两个等长有序序列的中位数。

相关知识
如何求解？
对于含有n个元素的有序序列a[s…t]，当n为奇数时，中位数是出现在m=(s+t)/2（下取整）处；当n为偶数时，中位数下标有m=(s+t)/2（下取整）（下中位）和m=(s+t)/2+1（上取整）（上中位）两个。为了简单，仅考虑中位数为m=(s+t)/2（下取整）处。
采用二分法求含有n个有序元素的序列a、b的中位数的过程如下：
（1）若n=1，较小者为中位数。
（2）其他又分为3种情况。
分别求出a、b的中位数a[m1]和b[m2]：
　　① 若a[m1]=b[m2]，则a[m1]或b[m2]即为所求中位数，算法结束。
② 若a[m1]<b[m2]，则舍弃序列a中前半部分（较小的一半），同时舍弃序列b中后半部分（较大的一半）要求舍弃的长度相等。
③ 若a[m1]>b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。舍弃一半即n/2个元素。

编程要求
根据提示，在右侧编辑器补充代码，计算并输出两个等长有序序列的中位数。

测试说明
平台会对你编写的代码进行测试
测试输入：5
11，13，15，17，19
2，4，6，8，20

输出结果：
a:11 13 15
b:6 8 20
a:11 13
b:8 20
a:11
b:20
中位数:11

开始你的任务吧，祝你成功！

package step3;
import java.util.Scanner;
import java.util.Arrays;
public class MIdNum{/begin// 合并两个已排序数组，并返回中位数的一个数值public static int findMedianSortedArrays(int[] a, int[] b) {while (a.length > 1 && b.length > 1) {int amid = a[a.length / 2];int bmid = b[b.length / 2];// 特殊情况：数组长度为2时直接取第一个元素、、如果数组为2，取第一个元素if (a.length == 2) {amid = a[0];bmid = b[0]; // }// 根据中位数进行数组的切割if (amid < bmid) {a = Arrays.copyOfRange(a, a.length / 2, a.length); // 保留后半段b = Arrays.copyOf(b, (b.length + 1) / 2); // 保留前半段} else {b = Arrays.copyOfRange(b, b.length / 2, b.length); // 保留后半段a = Arrays.copyOf(a, (a.length + 1) / 2); // 保留前半段}// 打印当前数组状态System.out.print("a:");for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");  // 打印空格}System.out.println();  // 打印换行System.out.print("b:");for (int i = 0; i < b.length; i++) {System.out.print(b[i] + " ");}System.out.println();}// 返回最终的中位数if (a.length == 0) return b[0];if (b.length == 0) return a[0];return Math.min(a[0], b[0]);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入数组的长度int n = scanner.nextInt();scanner.nextLine(); // 输入第一个数组String[] aInput = scanner.nextLine().split("\\s+");int[] a = new int[aInput.length];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(aInput[i].trim());}// 输入第二个数组String[] bInput = scanner.nextLine().split("\\s+");int[] b = new int[bInput.length]; for (int i = 0; i < n; i++) {b[i] = Integer.parseInt(bInput[i].trim());}// 对数组进行排序Arrays.sort(a);Arrays.sort(b);// 计算并输出中位数int median = findMedianSortedArrays(a, b);  // 返回一个int类型的System.out.print("中位数:"+ median);// 关闭扫描器scanner.close();  // 节省空间，不然浪费资源}
}