Search for a command to run...
Initialization
A partition is correct when everything left of both cuts is ≤ everything right of them. Search cut positions 0…4 in A.
Partition by Binary Search
1function median(arr1, arr2) {2 const n1 = arr1.length, n2 = arr2.length;3 4 // Always binary search the shorter array5 if (n1 > n2) return median(arr2, arr1);6 //n1: 4n2: 5left: 5low: 0high: 47 const n = n1 + n2;8 const left = Math.floor((n1 + n2 + 1) / 2);9 10 let low = 0, high = n1;11 while (low <= high) {12 const mid1 = Math.floor((low + high) / 2);13 const mid2 = left - mid1;14 15 const l1 = (mid1 > 0) ? arr1[mid1 - 1] : -Infinity;16 const r1 = (mid1 < n1) ? arr1[mid1] : Infinity;17 const l2 = (mid2 > 0) ? arr2[mid2 - 1] : -Infinity;18 const r2 = (mid2 < n2) ? arr2[mid2] : Infinity;19 20 // Both crossing pairs in order — partition is valid21 if (l1 <= r2 && l2 <= r1) {22 if (n % 2 === 1) return Math.max(l1, l2);23 return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;24 }25 else if (l1 > r2) high = mid1 - 1;26 else low = mid1 + 1;27 }28 return 0;29}