# 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.
• 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:

Code:

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

Double pointers with O(m+n)