package code;
/*
 * 4. Median of Two Sorted Arrays
 * O(logN)
 * Hard
 * Array, Binary Search, Divide and Conquer
 * 
 *       O(log(min(m,n))  
 */
public class lc4 {
    public static void main(String[] args) {
        int[] nums1 = {1,2};
        int[] nums2 = {3,4};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size1 = nums1.length;
        int size2 = nums2.length;
        if(size1>size2)
            return findMedianSortedArrays(nums2,nums1);

        int low = 0;
        int high = nums1.length;

        while(lownums2[j]){  //i
                //need reduce i
                high = i-1;
            }else if(inums1[i]){ //i
                //need increase i
                low = i+1;
            }else{
                //find correct i
                int l,r;
                if(i==0) {
                    //nums1  l
                    l = nums2[j-1];
                }else if(j==0){
                    //nums2 l
                    l = nums1[i-1];
                } else{
                    l = Math.max(nums1[i-1],nums2[j-1]);
                }

                if((size1+size2)%2==1)
                    return l;

                if(i==size1){
                    //nums1  r
                    r = nums2[j];
                }else if(j==size2){
                    //nums2  r
                    r = nums1[i];
                }else{
                    r = Math.min(nums1[i],nums2[j]);
                }
                return (l+r)*1.0/2;
            }
        }
        return -1;
    }
}