Given two sorted arrays, return the median of all their numbers together. It must run in O of log of m plus n.
DSA Animator › DSA Revision › Binary Search › Median of Two Sorted Arrays
Remember: binary search the cut, not the values. Left max at most right min means the cut is right. The video solves Median of Two Sorted Arrays (LeetCode 4, Hard) with the Binary Search on Partition pattern from the Binary Search topic, and you can replay every step in the interactive Median of Two Sorted Arrays animation.
Given two sorted arrays, return the median of all their numbers together. It must run in O of log of m plus n.
For 1, 3, 8 and 2, 7, 10, the merged order is 1, 2, 3, 7, 8, 10. The median is 3 plus 7 over 2, which is 5.
Merging both arrays is O of m plus n. Instead, we only need to find where the left half ends.
Cut the shorter array at i and the longer one at j, so that the left side holds half of all numbers. The cut is correct when every number on the left is at most every number on the right. That means A left is at most B right, and B left is at most A right. Binary search i, and move it right when B left is too big, or left when A left is too big.
Try i equal to 1 and j equal to 2. A left is 1 and B right is 10, which is fine, but B left 7 is bigger than A right 3. So move i right, to 2, and j becomes 1. Now A left 3 is at most B right 7, and B left 2 is at most A right 8, so the cut is valid. The median is the bigger of 3 and 2, plus the smaller of 8 and 7, over 2, which is 5.
In code, binary search i over the shorter array, and set j as half minus i. Use minus infinity and plus infinity when a cut is at an edge. If the cut is valid, return the median from the four border values. Otherwise move low or high, so it's O of log of the smaller length.
Remember: binary search the cut, not the values. Left max at most right min means the cut is right.