class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if (len % 2 == 1) {
            // total len is odd number, so the middle number is median
            return findKSmallest(nums1, 0, nums2, 0, len/2 + 1);
        }else {
            int mid1 = findKSmallest(nums1, 0, nums2, 0, len/2);
            int mid2 = findKSmallest(nums1, 0, nums2, 0, len/2 + 1);
            return (mid1 + mid2)/ 2.0;
        }

    }

    private int findKSmallest(int[] a, int aLeftIndex, int[] b, int bLeftIndex, int k) {

        int m = a.length - aLeftIndex;
        int n = b.length - bLeftIndex;
        // make the first array always shorter than the second array for better coding
        if (m > n) {
            return findKSmallest(b, bLeftIndex, a, aLeftIndex, k);
        }

        if (m == 0) {
            return b[bLeftIndex + k - 1];
        }
        if (k == 1) {
            return Math.min(a[aLeftIndex], b[bLeftIndex]);
        }
        // if the first array length is < k/2, then look for the whole array
        int p = m < k / 2 ? m : k / 2;
        int q = k - p;

        if (a[aLeftIndex + p - 1] == b[bLeftIndex + q - 1]) {
            return a[aLeftIndex + p - 1];
        } else if (a[aLeftIndex + p - 1] < b[bLeftIndex + q - 1]) {
            return findKSmallest(a, aLeftIndex + p , b, bLeftIndex, k - p); // since the left part of a array is smaller than the left part of b,  narrow the search range to leftindex+p, to length + 1
        } else {
            return findKSmallest(a, aLeftIndex , b, bLeftIndex + q , k - q);
        }
    }




}