# Leetcode 4 - Median of two sorted arrays

`Note:`

- Update: I keep forgetting how to solve it in
`O(log(m+n))`

, so I’ll just stick to`double pointer`

way. Be careful of edge cases like one of them is empty or they have same elements like`[0,0], [0,0]`

. - It requires
`O(log(m+n))`

time complexity, apparently, we need`binary search`

. - How to find the
`median`

? The median separates the array in half. - For convenience, we use binary search on the shorter array between nums1 and nums2. If nums2 is shorter than nums1, we swtich them.
- First, we get the
`index of median`

of`nums1`

using`(start + end) >> 1`

. Here, both operands are indexes. By basic math, the cut point in nums2 should be`half - i - 2`

. Half is the half length of nums1 and nums2 together, we substract (i+1) from it, which is the`length`

of`first part`

of nums1. But because we need`index`

, we still need to minus 1. `L1 = nums[i], R1 = nums[i+1]`

.`L2 = nums[j], R2 = nums[j+1]`

.- When can we say we’ve found the result?
`L1 <= R2 && L2 <= R1`

. - What if we didn’t?
- If
`L1 > R2`

, we need to make`L1`

shorter, so`end = i - 1`

. If`L2 > R1`

, which means`L1`

is too short. We need to make i bigger,`start = i + 1`

.

- If
- For example, when
`L1 > R2`

, what would happen will be like

`Question:`

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,2], nums2 = [3,4] |

`Code:`

`Binary search with O(log(m+n))`

1 | /** |

`Double pointers with O(m+n)`

1 | /** |