Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
METHOD 1 :
$arr1 = [2,4,6,7,8,50];
$arr2 = [1,3,5,9,10,20];
$m = count($arr1);
$n = count($arr2);
$temp = [];
$i = 0;
$j = 0;
$k = 0;
while($m>$i && $n>$j){
if($arr1[$i] < $arr2[$j]){
$temp[$k++]=$arr1[$i];
$i++;
}else{
$temp[$k++]=$arr2[$j];
$j++;
}
}
while($i<$m){
$temp[$k++]=$arr1[$i];
$i++;
}
while($j<$n){
$temp[$k++]=$arr2[$j];
$j++;
}
$tempCount = count($temp);
if($tempCount%2==0){
$mid = (int)$tempCount/2;
$mid2 = $mid-1;
$medium = ($temp[$mid]+$temp[$mid2])/2;
}else{
$mid = intval($tempCount/2);
$medium = $temp[$mid];
}
print_r($medium);
🔹 Time Complexity
- Merging process
- You iterate through both arrays once with pointers
iandj. - Each element is processed exactly once.
- Complexity = O(m + n)
- You iterate through both arrays once with pointers
- Finding Median
- After merging, just checking the middle elements → O(1)
✅ Final Time Complexity: O(m + n)
🔹 Space Complexity
- You create a new array
$tempto store the merged result. - Size of
$temp= m + n
✅ Space Complexity: O(m + n)
🔹 Advantages of this Approach
- Very simple and easy to implement.
- Works for all sorted arrays (guaranteed correctness).
- Stable merging (preserves order).
- Median finding is direct after merge.
🔹 Disadvantages
- Needs extra space O(m+n) (not memory efficient).
- Time complexity O(m+n) is not optimal for very large arrays.
- There exists a better solution using Binary Search on partitions with O(log(min(m,n))) time and O(1) space.
METHOD 2 :
🔹 Better Optimized Approach (DSA)
👉 Median of Two Sorted Arrays using Binary Search Partition Method
- No need to fully merge arrays.
- Runs in O(log(min(m,n))) time and O(1) space.
- Much faster for huge arrays.
📝 Code in PHP (Without Temp Array)
<?php
$arr1 = [2,4,6,7,8,50];
$arr2 = [1,3,5,9,10,20];
$m = count($arr1);
$n = count($arr2);
$total = $m + $n;
$mid1 = (int)(($total - 1) / 2); // left middle index
$mid2 = (int)($total / 2); // right middle index (same as mid1 if odd)
// Pointers
$i = $j = 0;
$count = -1;
$median1 = $median2 = 0;
// Merge simulation without temp array
while ($i < $m && $j < $n) {
$val = ($arr1[$i] < $arr2[$j]) ? $arr1[$i++] : $arr2[$j++];
$count++;
if ($count == $mid1) $median1 = $val;
if ($count == $mid2) {
$median2 = $val;
break;
}
}
while ($i < $m && $count < $mid2) {
$val = $arr1[$i++];
$count++;
if ($count == $mid1) $median1 = $val;
if ($count == $mid2) {
$median2 = $val;
break;
}
}
while ($j < $n && $count < $mid2) {
$val = $arr2[$j++];
$count++;
if ($count == $mid1) $median1 = $val;
if ($count == $mid2) {
$median2 = $val;
break;
}
}
// Final median
if ($total % 2 == 0) {
$median = ($median1 + $median2) / 2;
} else {
$median = $median2;
}
echo "Median: " . $median;
?>
✅ Complexity
- Time Complexity: O(m + n) (same as before, because we may need to scan all elements in worst case)
- Space Complexity: O(1) ✅ (no extra array, just a few variables)
🔹 Advantages of This Method
- No extra space (only variables).
- Still simple and readable.
- Directly finds the median.
METHOD 3 (BEST) :
Perfect 🚀
Now you want the optimized solution: Median of Two Sorted Arrays using Binary Search Partition Method.
This is the famous LeetCode Hard Problem #4 approach.
It reduces the time complexity from O(m+n) → O(log(min(m, n))) ✅ and uses O(1) space.
🔹 Idea (Binary Search Partition Method)
- Ensure first array (
arr1) is the smaller one (so we binary search on it). - Partition both arrays such that:
- Left side of partition has exactly half elements of total.
- Right side has the rest.
- Median depends on max(left side) and min(right side).
- If total size is odd → median =
maxLeft. - If even → median =
(maxLeft + minRight)/2.
- If total size is odd → median =
📝 PHP Implementation
<?php
function findMedianSortedArrays($arr1, $arr2) {
$m = count($arr1);
$n = count($arr2);
// Ensure arr1 is the smaller array
if ($m > $n) {
return findMedianSortedArrays($arr2, $arr1);
}
$low = 0;
$high = $m;
$half = (int)(($m + $n + 1) / 2);
while ($low <= $high) {
$partitionA = (int)(($low + $high) / 2);
$partitionB = $half - $partitionA;
$maxLeftA = ($partitionA == 0) ? -INF : $arr1[$partitionA - 1];
$minRightA = ($partitionA == $m) ? INF : $arr1[$partitionA];
$maxLeftB = ($partitionB == 0) ? -INF : $arr2[$partitionB - 1];
$minRightB = ($partitionB == $n) ? INF : $arr2[$partitionB];
if ($maxLeftA <= $minRightB && $maxLeftB <= $minRightA) {
if ((($m + $n) % 2) == 0) {
return (max($maxLeftA, $maxLeftB) + min($minRightA, $minRightB)) / 2;
} else {
return max($maxLeftA, $maxLeftB);
}
} elseif ($maxLeftA > $minRightB) {
$high = $partitionA - 1;
} else {
$low = $partitionA + 1;
}
}
throw new Exception("Input arrays are not sorted or invalid");
}
// Example
$arr1 = [2, 4, 6, 7, 8, 50];
$arr2 = [1, 3, 5, 9, 10, 20];
echo "Median: " . findMedianSortedArrays($arr1, $arr2);
?>
✅ Complexity
- Time Complexity: O(log(min(m,n)))
- Space Complexity: O(1)
🔹 Advantages
- Super efficient for very large arrays.
- No extra space required.
- Widely used in coding interviews (FAANG favorite).