Problem
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
Should be done in O(log(m+n))
Algorithm & Code
1. 找到merged array中mdedian的位置k & k-1 (分even & odd case)
2. 找到arr1中mdedian的位置m1 & m1-1
* binary search: find insert position s.t
* a[m1] <= b[m2-1] <= a[m1-1]
3. 找到arr2中mdedian的位置m2 & m2-1
* m2 = k - m1
4. 根据arr1[m1], arr1[m1-1], arr2[m2], arr2[m2-1],找到merged array 中的median
(图片来自花花酱blog:https://zxi.mytechroad.com/blog/algorithms/binary-search/leetcode-4-median-of-two-sorted-arrays/)