# 4. Median of Two Sorted Arrays

![](/files/-Ml4n86gp0ANc-4WcT63)

![](/files/-Ml4nBSU9H-jsZ0v44Sz)

time: O(log(m+n))

space: O(1)

```java
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

```java
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)
    

*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/divide-and-conquer/4.-median-of-two-sorted-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.