There are two sorted arrays A and B of size
asked
1337c0d3r ♦♦ |

If you read my previous post: Find the k-th Smallest Element in the Union of Two Sorted Arrays, you know that this problem is somewhat similar. In fact, the problem of finding the median of two sorted arrays when ( You might ask: Why not adapt the previous solution to this problem? After all, the previous algorithm solves a more general case. Well, I've tried that and I didn't consider the previous solution is easily adaptable to this problem. The main reason is because when ( Similar to finding the k-th smallest, the divide and conquer method is a natural approach to this problem. First, we choose A Two sorted arrays A and B. i is chosen as m/2 and j is chosen as n/2. A _{i} and B_{j} are middle elements of A and B. If A_{i} < B_{j}, then the median must be between A_{i} and B_{j} (inclusive). Similarly with the opposite.The main idea illustrated above is mostly right, however there is one more important invariant we have to maintain. It is entirely possible that the number of elements being disposed from each array is different. Look at the example above: If A Therefore, an important invariant we have to maintain is:
This could be easily achieved by choosing the number of elements to dispose from each array to be ( k = min(i, n-j-1) when A Figuring out how to subdivide the problem is actually the easy part. The hard part is figuring out the base case. (ie, when should we stop subdividing?) It is obvious that when Finally, implementing the above idea turns out to be an extremely tricky coding exercise. Before looking at the solution below, try to challenge yourself by coding the algorithm. If you have a more elegant code to this problem, I would love to hear from you!
Shortly after I fixed that bug, I discovered another edge case myself which my previous code failed to handle. An example of one of the edge cases is: A = { 1, 2, 4, 8, 9, 10 } B = { 3, 5, 6, 7 } The above conditions ( The reason is because the number 5 is discarded in the first iteration, while it should be considered in the final evaluation step of the median. To resolve this edge case, we have to be careful not to discard the neighbor element when its size is even. Here are the corrected conditions ( k = min(i-1, n-j-1) when ABelow is the bug-free code after going through a lengthy rigorous testing of all possible edge cases. (Not for the faint of heart!)
In general, The above approaches (including mine) to handle the base case are not recommended due to tricky implementation. How about Binary Search? We can use binary search to find the correct position to insert elements from the shorter array into the longer array, thus completing the merge (You don't have to
answered
1337c0d3r ♦♦ |

class Solution {
};
answered
weibest |

answered
sillyjims |

A java implementation based on MIT handout. I just realized that the algorithm given in comments (http://leetcode.com/2011/03/median-of-two-sorted-arrays.html#comment-1053) didn't validate index of B[j] (in the case where m+n is even. Also, the mod can be replaced with bit-operation, which is much cheaper.
answered
n00tc0d3r |

answered
xiaoc10 |

This solution is greatly inspired by the Manacher's algorithm which is described longest palindromic substring. By inject the median of two ajacent numbers in the array, we don't need to take the array's oddness into consideration. Given two sorted arrays Small and Big, Small.size()<= Big.size(). For example Small= {1,2,3,4}, Big = {5,6,7,8} Inflated Small is {1,1.5,2,2.5,3,3.5,4} and inflated Big is {5,5.5,6,6.5,7,7.5,8}. Constructing the inflated arrays would require O(n),which is undesirable. We can use the function get(int[] array,pos) to get array[pos] whenever we need such a value,see the following codes. We just call the array inflated Small as small and inflated big as big for simplicity. The tricky part is that we can constantly reduce the size of small and big by the same offset untill the length of small is 1 or 3. Why? Because Small (the base of inflated Small or small) at most contribute two elements that determines the final median. When the size of small and big are small enough we can easily compute the median by simply sorting them. In this program, the size of small is constantly reduced by approximately half. By approximately I mean the two numbers neighboring the median of small is never changed in each round. (Notice the length of small or inflated Small is always odd, so there always exists a median). while(size of small >3) {
} When the above loop is done, the size of big can still be very big. You can prove that the median of small and the 5 elements closest to the center of B is the median of the two sorted array.
answered
yangmo |

seems the comment:
should be:
answered
steve |

answered
cheninnerv |

A simpler solution without recursion. O(log(m+n)).
answered
zhangxu |