4. Median of Two Sorted Arrays

time: O(log(m+n))

space: O(1)

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int n = A.length + B.length;
        
        if (n % 2 == 0) { // even numbers count, need do average
            return (
                findKth(A, 0, B, 0, n/2) + 
                findKth(A, 0, B, 0, n/2 + 1)
            ) / 2.0;
        }
        
        return findKth(A, 0, B, 0, n/2 + 1); // ex: 3/2 = 1, 1+1, find 2th (median)
    }

    // find kth number of two sorted array
    public static int findKth(int[] A, int startOfA,
                              int[] B, int startOfB,
                              int k){ 
        
        // A is too long, so return b's kth, (index: k-1)
        if (startOfA >= A.length) {
            return B[startOfB+k-1];
        }
        if (startOfB >= B.length) {
            return A[startOfA+k-1];
        }
    
        // finally only 1 number need to choose from A[] or B[]
        if (k == 1) {
            return Math.min(A[startOfA], B[startOfB]);
        }
        
        int offset = k/2-1; // k is th, so index need -1
        // cal k/2 position value
        int halfKthOfA = startOfA + offset < A.length
            ? A[startOfA + offset]
            : Integer.MAX_VALUE;
        
        int halfKthOfB = startOfB + offset < B.length
            ? B[startOfB + offset]
            : Integer.MAX_VALUE; 
        
        // 1 2 3, if whant to have new start 3, k=2, it's start+k = 0 + 2 = 2 (index 2 is 3) 
        // k/2 position A value is smaller, discard A pre k/2, size become half: (k - k/2)
        if (halfKthOfA < halfKthOfB) {
            return findKth(A, startOfA + k/2, B, startOfB, k - k/2);
        } else {
            return findKth(A, startOfA, B, startOfB + k/2, k - k/2);
        }
    }
}

more comment

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if (len % 2 == 0) { // even length
            return (findKth(nums1, 0, nums2, 0, len/2) + findKth(nums1, 0, nums2, 0, len/2+1))/2.0;
        }
        return findKth(nums1, 0, nums2, 0, len/2+1);
    }
    private int findKth(int[] nums1, int startNum1, int[] nums2, int startNum2, int k) {
        // edge case
        if (startNum1 >= nums1.length) { // index: kth need -1
            return nums2[startNum2+k-1];
        }
        if (startNum2 >= nums2.length) { 
            return nums1[startNum1+k-1];
        }
        
        if (k == 1) {
            return Math.min(nums1[startNum1], nums2[startNum2]);
        }
        
        int offset = k/2 - 1; //index
        int halfKValue1 = startNum1 + offset < nums1.length ? nums1[startNum1 + offset]: Integer.MAX_VALUE; // shorter one give max, dont discard shorter one
        int halfKValue2 = startNum2 + offset < nums2.length ? nums2[startNum2 + offset]: Integer.MAX_VALUE;
        
        // discard smaller one
        if (halfKValue1 < halfKValue2) {
            return findKth(nums1, startNum1+k/2, nums2, startNum2, k - k/2);
        } else {
            return findKth(nums1, startNum1, nums2, startNum2+k/2, k - k/2);
        }
    }
}

/*
general solution: merge sort idea, than find median: O(m+n)

how to improve? we want O(log(m+n))

main() {
    if (even) {
        return (findKth(, 2/n + 1) + findKth(, 2/n) )/2 // median is (2/n + 1 +2/n)/2
    }
    return findKth(, 2/n + 1) // median is 2/n + 1
}

findKth()

0. edge case 
but have some edgae case

startIndexA >= nums1 len
    return nums2[startIndexB+k-1]
startIndex >= nums1 len
    return nums1[startIndexA+k-1]

1. terminal condition:
if (k == 1) {
    return min(nums1[startIndexA], nums2[startIndexB])
}

2.
valueA = nums1 find k/2 position's value
valueB = nums2 find k/2 position's value

3. 
if (valueA < valueB)
    we can discard A's pre k/2 data, so size become remain k/2 (so time complexiy becomes log m)
else 
    we can discard A's pre k/2 data, so size become remain k/2 (so time complexiy becomes log m)
    

*/