Let’s call our two arrays A and B, where they have sizes a and b. A key insight is that we need to partition both arrays such that the left of both will be the same size as the right of both. The only exception is if we an odd total number of elements, in which case we will put the extra element in the left partition. Our partition index will be the start of the right hand partition. The partition can be before the first element 0, and up to after the last element arr.size(). Start with the smallest array as A. Start with our binary search constraints (hi and lo) as 0 to arr.size(). Calculate partitionA as (lo+hi)/2. Calculate partitionB as (a+b+1)/2-partA, where a and b are lengths of the arrays. Calculate the elements next to the partition. One thing to note here is that we use INF and -INF if an array’s partition is empty, which enables our comparisons to work. Check if we have reached our end condition, which is maxALeft <= minBRight and maxBRight <= minALeft, and if we have then return the value closest to the partition from left if odd or average of two closest values to partition from both left and right if even. Otherwise if not end condition the adjust the binary search bounds and loop again.
Key points:
- Understand that we will partition both arrays and they need to be partitioned such that both left sides are the same size (or one more) than both right sides.
- Understand we can use binary search to try to find the correct partition position in log(len) time.
- The correct partition position will be when maxALeft <= minBRight and maxBLeft <= minARight. Where maxALeft is the biggest value in the left partition of array A.
- The partition can be between any of the numbers in the array and can be before the first element and after the last element.
- Start with binary search of first array (smallest array) to be lo=0 and hi=a.
- Calculate partition A = (lo + hi) / 2
- Calculate partition B = (a+b+1) / 2 – partA
- Check if we are at the correct end partition position using calculated boundary values and if so then calculate median. If odd total number of elements then median is biggest value in left partition, which is: max(maxALeft, maxBLeft). If even then we need to get average of biggest in left and smallest in right, which is: max(maxALeft, maxBLeft)+min(minARight, minBRight) / 2.
- If not at end partition position then step forward our binary search. If partition A is too far to right (maxAleft > minBRight) then we need to move our search to left half of search bounds, so: hi = partitionA – 1. The -1 is important as it allows us to get in front of the array. Otherwise move search to right half of search bounds, so: lo = partitionA + 1
