Median of two sorted arrays, explained with binary search
The question: Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays.
Binary search for a cut in the smaller array so the left halves hold half the numbers and every left value is at most every right value. The median sits at the cut. Time O(log min(m, n)), space O(1).
The median of two sorted arrays problem (LeetCode 4) explained step by step: the partition idea, moving the cut with binary search, a worked example and the Python code, in O(log min(m, n)) time.
Step-by-step transcript
The question
Two sorted arrays, and we want their median, without merging them. Here's the trick.
What we know and the plan
We have two sorted arrays. Let's call them A, of size m, and B, of size n. We need the median of all the numbers together. Merging works, but it takes m plus n steps, and we can do much better. The key idea: we don't need the merged array. We only need to find the right place to cut. And a cut position is something we can binary search.
The idea: cut both arrays
First, decide how many numbers go on the left side. That's m plus n plus one, over two, rounded down. The plus one puts the extra number on the left when the total is odd. Now cut A after i numbers, and B after j numbers. Together, the left pieces must hold exactly half. So once we pick i, j is fixed. j is half minus i. We only search for one number, i. When is a cut correct? The last number on A's left must be at most the first number on B's right, and the last number on B's left must be at most the first on A's right. Then everything on the left is smaller than everything on the right.
Moving the cut
If A's left side has a number that's too big, we took too much from A. Move the cut left. If B's left side has a number that's too big, we took too little from A. Move the cut right. When the cut is correct, and the total is odd, the median is the biggest number on the left side. When the total is even, it's the average of the biggest on the left and the smallest on the right.
Try it on an example
Let's try A equals one, three, eight, and B equals seven, nine, ten, eleven. Three plus four is seven numbers, so four go on the left. Search i from zero to three. The middle is one, so j is three. But ten, on B's left, is bigger than three, on A's right. Move right. Now i is two, and j is two. Nine is still bigger than eight. Move right again. Now i is three, and j is one. Eight is at most nine, and seven is at most infinity, because A has nothing left on the right. The cut is correct. Seven numbers is odd, so the median is the bigger of eight and seven. Eight.
The code
Here's the code. First, make sure A is the smaller array, so we binary search the short one and j never goes negative. Work out the sizes and half, and search i anywhere from zero to m. Each round, try the middle i, and j follows from it. Read the four numbers around the cut. If a side is empty, use minus infinity or infinity, so the comparison always works. If the cut is correct, return the median: the biggest on the left for odd totals, or the average of the two middle numbers for even. Otherwise, move the cut left or right, exactly as we did by hand.
The answer
Each round halves the search, so it runs in log of the smaller size, with constant extra space.
Checking the answer
To check, merge the example by hand: one, three, seven, eight, nine, ten, eleven. The middle number is eight. It matches.
The common mistake
A common mistake is merging first. It gives the right answer, but it's too slow for this question. And always binary search the smaller array.
stuck on a different question?
Ask Doubtster in chat for free and get the steps. Turn it into a video like this one when you want to see it worked out.
more example lessons
Made with the Doubtster video engine. AI explanations can contain mistakes, so check important answers with your teacher.