public class UpMedian{
    //求相同長度排序數(shù)組的中位數(shù)
    public static int getUpMedian(int[] arr1,int start1,int end1,int[] arr2,int start2,int end2) {
        if(arr1==null || arr1.length<=0 || arr2==null || arr2.length<=0) {
            System.out.println("Array is valid");
            return -1;
        }
        
        if(arr1.length!=arr2.length) {
            System.out.println("Array length is valid");
            return -1;
        }
        
        int middle1 = 0;
        int middle2 =0;
        //用來區(qū)分數(shù)組長度為奇偶數(shù)
        int offset = 0;
        
        while(start1 < end1) {
            middle1 = (start1+end1)>>1;
            middle2 = (start2+end2)>>1;
            offset = ((end1-start1+1)&1)^1;
            
            if(arr1[middle1] > arr2[middle2]) {
                end1=middle1;
                start2=middle2+offset;
            } else if(arr1[middle1] < arr2[middle2]) {
                start1 = middle1 +offset;
                end2 = middle2;
            } else {
                return arr1[middle1];
            }
        }
        
        return Math.min(arr1[start1], arr2[start2]);
    }

    public static int fingKthNum(int[] arr1, int[] arr2, int k) {
        if(arr1==null || arr2==null || arr1.length<=0 || arr2.length<=0) {
            throw new RuntimeException("Array is valid");
        }
        
        if(k<1 || k>(arr1.length+arr2.length)) {
            throw new RuntimeException("kth is valid");
        }
        
        int res = 0;
        int[] longs = arr1.length>arr2.length ?arr1 : arr2;
        int[] shorts = arr1.length>arr2.length ?arr2 : arr1;
        
        int l = longs.length;
        int s = shorts.length;
        
        if(k<=s) {
            res = getUpMedian(arr1, 0, k-1, arr2, 0, k-1);
        } else if(k<=l) {
            if(longs[k-s-1]>=shorts[s-1]) {
                res = longs[k-s-1];
            } else {
                res = getUpMedian(shorts, 0, s-1, longs, k-s, k-1);
            }
        } else if(k>l){
            if(longs[k-s-1]>=shorts[s-1]) {
                res = longs[k-s-1];
            } else if(shorts[k-l-1]>=longs[l-1]) {
                res = shorts[k-l-1];
            } else {
                res = getUpMedian(shorts, k-l, s-1, longs, k-s, l-1);
            }
        }
        return res;
    }
    

    public static void main(String[] args) {
        int[] a1 = {1,2,5,7};
        int[] a2 = {2,3,8,10};
        System.out.println(fingKthNum(a1, a2, 4));
    }
}