Problem context and objectives
Mission briefing
Signal rescue operator · A beacon is hidden inside an ordered frequency band
Lock onto the signal without testing every frequency: The Median Partition.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Binary search on a partition matches the clues
- 2Keep this true after every move: the two cuts place the required number of values on the combined left side
- 3Reach the result within O(log min(m, n))
Rules and pressure
- Target cost: O(log min(m, n))
- State rule: the two cuts place the required number of values on the combined left side
New words in this mission
Open a term for a plain-language explanation.partition or shard+
One slice of a larger dataset or workload. Splitting work raises capacity, but cross-slice operations become harder.
Lesson 1 of 3
Live algorithm trace
Binary search on a partition
Complete execution1 of 9
Search cut positions only in the smaller three-value array A.
1
binary search the smaller array2
cutA = midpoint3
cutB = half - cutA4
read four partition borders5
if leftA > rightB: move cutA left6
if leftB > rightA: move cutA right7
otherwise compute medianA = [1,3,8]B = [7,9,10,11]half = 4
Truth to preserve / Cost target
Truth to preserve
the two cuts place the required number of values on the combined left side
Cost target
O(log min(m, n))
Partition the smaller array and derive the matching cut in the larger one so the left side holds half the values. A valid partition has both left maxima no greater than both right minima.
Your call · What should guide every step of this algorithm?