Median of Two Sorted Array ​
Median of Two Sorted Array — LeetCode
Find the median of two sorted arrays in O(log(min(m, n))) time.
Approach ​
Idea is to do binary search on the smaller array, so that we find the left half and right half. Do it till the partition is found, NOT l<=r. Also, mid is calculated by Math.Floor, not integer division. half = len(a) + len(b).
Then find how many elements of b will be part of the left half by binary search. m -> pointer to bj = half - m - 2 (the -2 is for index adjustment). j will be pointer to a. Partition is found when: a[j] < b[m + 1] and b[m] < a[j+1]. If first condition is wrong, set l = m + 1. if second condition is wrong, r = m - 1. Median is min(aRight, bRight) if odd and max(aLeft, bLeft) + min(aRight, bRight) is even. Lots of gotchas: Better to think of right of both arrays as +inf, and left of both arrays as -inf.
Remarks ​
Wont understand s- without the video: https://www.youtube.com/watch?v=q6IEA26hvXc