# 0004. Median of Two Sorted Arrays

<https://leetcode.com/problems/median-of-two-sorted-arrays>

## Description

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return **the median** of the two sorted arrays.

The overall run time complexity should be `O(log (m+n))`.

**Example 1:**

```
**Input:** nums1 = [1,3], nums2 = [2]
**Output:** 2.00000
**Explanation:** merged array = [1,2,3] and median is 2.
```

**Example 2:**

```
**Input:** nums1 = [1,2], nums2 = [3,4]
**Output:** 2.50000
**Explanation:** merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
```

**Example 3:**

```
**Input:** nums1 = [0,0], nums2 = [0,0]
**Output:** 0.00000
```

**Example 4:**

```
**Input:** nums1 = [], nums2 = [1]
**Output:** 1.00000
```

**Example 5:**

```
**Input:** nums1 = [2], nums2 = []
**Output:** 2.00000
```

**Constraints:**

* `nums1.length == m`
* `nums2.length == n`
* `0 <= m <= 1000`
* `0 <= n <= 1000`
* `1 <= m + n <= 2000`
* `-106 <= nums1[i], nums2[i] <= 106`

## ac1: iterative

```java
// iterative version, very ugly and tedious
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // findKth, k=(m+n)/2
        // M[k/2], N[k/2].  deduct k/2 each time. untill k == 1
        // if M[k/2] < N[k/2], 'delete' <-[k/2]
        // if (m+n) % 2 == 0, (M[0]+N[0]) / 2, else M[0]

        // corner cases
        if (nums1.length == 0 && nums2.length == 0) return 0;

        return findKth(nums1, nums2, 0, 0);
    }

    private double findKth(int[] nums1, int[] nums2, int s1, int s2) {
        int k = (nums1.length + nums2.length + 1) / 2; // kth number 

        while (k > 1 && s1 < nums1.length && s2 < nums2.length) {
            int mid1 = s1+k/2-1 < nums1.length ? nums1[s1+k/2-1] : Integer.MAX_VALUE;
            int mid2 = s2+k/2-1 < nums2.length ? nums2[s2+k/2-1] : Integer.MAX_VALUE;
            if (mid1 < mid2) s1 += k/2;
            else s2 += k/2;
            k = k - k/2;
        }

        // get mid points
        int first = 0, second = 0;
        if (s1 >= nums1.length) {
            first = nums2[s2+k-1];
            if (s2+k < nums2.length) second = nums2[s2+k];
        } else if (s2 >= nums2.length) {
            first = nums1[s1+k-1];
            if (s1+k < nums1.length)second = nums1[s1+k];
        } else {
            first = nums1[s1] < nums2[s2] ? nums1[s1++] : nums2[s2++];
            if (s1 >= nums1.length) second = nums2[s2];
            else if (s2 >= nums2.length) second  = nums1[s1];
            else second = Math.min(nums1[s1],nums2[s2]);
        }

        // return result
        if ((nums1.length + nums2.length) % 2 != 0) {
            return (double) first;
        } else {
            return (double) (first+second) / 2;
        }
    }
}
```


---

# 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://jaywin.gitbook.io/leetcode/solutions/0004-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.