## Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

**Example 1:**

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

**Example 2:**

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

## Solution1

1 | class Solution: |

### Tips

For a sorted number `a`

of length `n`

, if `n`

is an odd number, the median is `a[n / 2 + 1]`

. If `n`

is even, the median `(a[n / 2] + a[n / 2 + 1]) / 2`

.

If we can find the `Kth`

element in the two series, we can solve the problem.

It may be desirable to set the number of `A`

elements in the series to be `n`

, and the number of elements in the series `B`

to be `m`

, and sort them in ascending order, and find the `kth`

small element.

Take `A[k / 2]`

`B[k / 2]`

comparison,If `A[k / 2] > B[k / 2]`

then the element sought is inevitably not in the `first k / 2`

elements of `B`

(proving counter-evidence)

On the contrary, it must not be in the `first k / 2`

elements of `A`

, so we can delete the `first k / 2`

elements of the A or B series, and find the remaining two series `k - k / 2`

small elements, so I got the same problem with the data size becoming smaller. If `k / 2`

is greater than a certain number of columns, the element sought must not be in the `first k / 2`

elements of the other series , recursively solved.

## Solution2

1 | class Solution: |

### Tips

In python, the time complexity of the function `len`

is `O(1)`

. The time complexity of the function `sort`

is `O(nlog(n))`

. `Timsort algorithm`

is used for `sorted`

in python.

So solution2 actually runs faster than solution1.