Reference: LeetCode
Difficulty: Hard

## Problem

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:

## Analysis

### Sorting

Put nums1 and nums2 into a new array nums, and sort nums.

Time: $O((m + n)\log{(m + n)})$
Space: $O(m + n)$

### Two Pointers

Use two pointers to locate the index of the median. Process the pointers carefully with some special cases.

Time: $O(m + n)$
Space: $O(1)$

Reference: Finding the Median of 2 Sorted Arrays in Logarithmic Time (Question 6)

The idea is to avoid merging two arrays, since merging takes $O(m + n)$ time. We can use binary search to optimize the two-pointer approach.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.