package question;

import java.util.Arrays;

/*
 @author: Roderland
 @create: 2020年09月24日---19:05
*/
public class Question4 {
 public static void main(String[] args) {
 //[1,3] [2]
 int[] nums1 = new int[]{3,4,5};
 int[] nums2 = new int[]{1,2,6,7,8};
 System.out.println(new Question4().findMedianSortedArrays(nums1, nums2));
 }

 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 if (nums1 == null || nums1.length == 0) return getMedian(nums2);
 if (nums2 == null || nums2.length == 0) return getMedian(nums1);
 return getMedian(nums1, nums2);
 }

 public double getMedian(int[] nums1, int[] nums2) {
 int r1 = nums1[nums1.length - 1];
 int r2 = nums2[nums2.length - 1];
 int l1 = nums1[0];
 int l2 = nums2[0];
 if (nums1.length == 1) return getMedian(nums2, nums1[0]);
 else if (nums2.length == 1) return getMedian(nums1, nums2[0]);
 else if (nums1.length == 2 && nums2.length == 2) {
 if (r1 <= l2) return getMedian(r1, l2);
 else if (r2 <= l1) return getMedian(r2, l1);
 else if (r2 > r1 && l2 > l1) return getMedian(r1, l2);
 else if (r1 > r2 && l1 > l2) return getMedian(r2, l1);
 else if (r1 > r2 && l2 > l1) return getMedian(r2, l2);
 else if (r2 > r1 && l1 > l2) return getMedian(r1, l1);
 }
 double median1 = getMedian(nums1);
 double median2 = getMedian(nums2);
 if (median1 == median2) return median1;
 else {
 int len = nums1.length < nums2.length ? nums1.length / 2 : nums2.length / 2;
 if (median1 < median2)
 return getMedian(Arrays.copyOfRange(nums1, len, nums1.length), Arrays.copyOf(nums2, nums2.length - len));
 else
 return getMedian(Arrays.copyOf(nums1, nums1.length - len), Arrays.copyOfRange(nums2, len, nums2.length));
 }
 }

 public double getMedian(int[] nums) {
 if ((nums.length & 1) == 1) return nums[nums.length / 2];
 else return getMedian(nums[nums.length / 2 - 1], nums[nums.length / 2]);
 }

 public double getMedian(int a, int b) {
 return (a + b) / 2d;
 }

 public double getMedian(int[] nums, int a) {
 int index = search(nums, a);
 int[] newNums = new int[nums.length + 1];
 for (int i = 0; i < newNums.length; i++) {
 if (i == index) newNums[i] = a;
 else if (i > index) newNums[i] = nums[i - 1];
 else newNums[i] = nums[i];
 }
 return getMedian(newNums);
 }

 public int search(int[] nums, int a) {
 int left = 0;
 int right = nums.length - 1;
 while (left < right) {
 int mid = (left + right) / 2;
 if (nums[mid] == a) return mid;
 else if (nums[mid] > a) {
 if (mid - 1 < 0) return 0;
 else if (nums[mid - 1] < a) return mid;
 right = mid - 1;
 } else {
 left = mid + 1;
 }
 }
 if (right == nums.length - 1 && a > nums[right]) return nums.length;
 return left;
 }
}