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;
    }
}