#include <limits.h>
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
// Always binary search on the smaller array
if (nums1Size > nums2Size)
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
int n = nums1Size, m = nums2Size;
int left = 0, right = n; // number of elements taken from nums1 into left half
int total = n + m;
int halfLeft = (total + 1) / 2; // size of left half (handles odd/even uniformly)
while (left <= right) {
int i = left + (right - left) / 2; // elements taken from nums1
int j = halfLeft - i; // elements taken from nums2
// Sentinels for out-of-range boundaries
int nums1Left = (i == 0) ? INT_MIN : nums1[i - 1];
int nums1Right = (i == n) ? INT_MAX : nums1[i];
int nums2Left = (j == 0) ? INT_MIN : nums2[j - 1];
int nums2Right = (j == m) ? INT_MAX : nums2[j];
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// Valid partition found
if (total % 2 == 1) {
return (double)(nums1Left > nums2Left ? nums1Left : nums2Left);
} else {
int a = nums1Left > nums2Left ? nums1Left : nums2Left;
int b = nums1Right < nums2Right ? nums1Right : nums2Right;
return (a + b) / 2.0;
}
} else if (nums1Left > nums2Right) {
right = i - 1; // too many from nums1, shrink
} else {
left = i + 1; // too few from nums1, grow
}
}
return 0.0; // unreachable if inputs are valid sorted arrays
}
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
// Always binary search on the smaller array
if (nums1.size() > nums2.size())
return findMedianSortedArrays(nums2, nums1);
int n = nums1.size(), m = nums2.size();
int left = 0,
right = n; // number of elements taken from nums1 into left half
int total = n + m;
int halfLeft =
(total + 1) / 2; // size of left half (handles odd/even uniformly)
while (left <= right) {
int i = left + (right - left) / 2; // elements taken from nums1
int j = halfLeft - i; // elements taken from nums2
// Sentinels for out-of-range boundaries
int nums1Left = (i == 0) ? INT_MIN : nums1[i - 1];
int nums1Right = (i == n) ? INT_MAX : nums1[i];
int nums2Left = (j == 0) ? INT_MIN : nums2[j - 1];
int nums2Right = (j == m) ? INT_MAX : nums2[j];
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// Valid partition found
if (total % 2 == 1) {
return max(nums1Left, nums2Left);
} else {
double a = max(nums1Left, nums2Left);
double b = min(nums1Right, nums2Right);
return (a + b) / 2.0;
}
} else if (nums1Left > nums2Right) {
right = i - 1; // too many from nums1, shrink
} else {
left = i + 1; // too few from nums1, grow
}
}
return 0.0; // unreachable if inputs are valid sorted arrays
}
};
package main
import "math"
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
// Always binary search on the smaller array
if len(nums1) > len(nums2) {
return findMedianSortedArrays(nums2, nums1)
}
n, m := len(nums1), len(nums2)
left, right := 0, n // number of elements taken from nums1 into left half
total := n + m
halfLeft := (total + 1) / 2 // size of left half (handles odd/even uniformly)
for left <= right {
i := left + (right-left)/2 // elements taken from nums1
j := halfLeft - i // elements taken from nums2
// Sentinels for out-of-range boundaries
nums1Left := math.MinInt32
if i != 0 {
nums1Left = nums1[i-1]
}
nums1Right := math.MaxInt32
if i != n {
nums1Right = nums1[i]
}
nums2Left := math.MinInt32
if j != 0 {
nums2Left = nums2[j-1]
}
nums2Right := math.MaxInt32
if j != m {
nums2Right = nums2[j]
}
if nums1Left <= nums2Right && nums2Left <= nums1Right {
// Valid partition found
if total%2 == 1 {
return float64(max(nums1Left, nums2Left))
}
a := max(nums1Left, nums2Left)
b := min(nums1Right, nums2Right)
return float64(a+b) / 2.0
} else if nums1Left > nums2Right {
right = i - 1 // too many from nums1, shrink
} else {
left = i + 1 // too few from nums1, grow
}
}
return 0.0 // unreachable if inputs are valid sorted arrays
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Always binary search on the smaller array
if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
int n = nums1.length, m = nums2.length;
int left = 0, right = n; // number of elements taken from nums1 into left half
int total = n + m;
int halfLeft = (total + 1) / 2; // size of left half (handles odd/even uniformly)
while (left <= right) {
int i = left + (right - left) / 2; // elements taken from nums1
int j = halfLeft - i; // elements taken from nums2
// Sentinels for out-of-range boundaries
int nums1Left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1Right = (i == n) ? Integer.MAX_VALUE : nums1[i];
int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2Right = (j == m) ? Integer.MAX_VALUE : nums2[j];
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// Valid partition found
if (total % 2 == 1) {
return Math.max(nums1Left, nums2Left);
} else {
double a = Math.max(nums1Left, nums2Left);
double b = Math.min(nums1Right, nums2Right);
return (a + b) / 2.0;
}
} else if (nums1Left > nums2Right) {
right = i - 1; // too many from nums1, shrink
} else {
left = i + 1; // too few from nums1, grow
}
}
return 0.0; // unreachable if inputs are valid sorted arrays
}
}
class Solution {
findMedianSortedArrays(nums1, nums2) {
// Always binary search on the smaller array
if (nums1.length > nums2.length) return this.findMedianSortedArrays(nums2, nums1);
const n = nums1.length, m = nums2.length;
let left = 0, right = n; // number of elements taken from nums1 into left half
const total = n + m;
const halfLeft = Math.floor((total + 1) / 2); // size of left half (handles odd/even uniformly)
while (left <= right) {
const i = left + Math.floor((right - left) / 2); // elements taken from nums1
const j = halfLeft - i; // elements taken from nums2
// Sentinels for out-of-range boundaries
const nums1Left = i === 0 ? -Infinity : nums1[i - 1];
const nums1Right = i === n ? Infinity : nums1[i];
const nums2Left = j === 0 ? -Infinity : nums2[j - 1];
const nums2Right = j === m ? Infinity : nums2[j];
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// Valid partition found
if (total % 2 === 1) {
return Math.max(nums1Left, nums2Left);
} else {
const a = Math.max(nums1Left, nums2Left);
const b = Math.min(nums1Right, nums2Right);
return (a + b) / 2.0;
}
} else if (nums1Left > nums2Right) {
right = i - 1; // too many from nums1, shrink
} else {
left = i + 1; // too few from nums1, grow
}
}
return 0.0; // unreachable if inputs are valid sorted arrays
}
}
class Solution:
def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
# Always binary search on the smaller array
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
n, m = len(nums1), len(nums2)
left, right = 0, n # number of elements taken from nums1 into left half
total = n + m
halfLeft = (total + 1) // 2 # size of left half (handles odd/even uniformly)
while left <= right:
i = left + (right - left) // 2 # elements taken from nums1
j = halfLeft - i # elements taken from nums2
# Sentinels for out-of-range boundaries
nums1Left = float("-inf") if i == 0 else nums1[i - 1]
nums1Right = float("inf") if i == n else nums1[i]
nums2Left = float("-inf") if j == 0 else nums2[j - 1]
nums2Right = float("inf") if j == m else nums2[j]
if nums1Left <= nums2Right and nums2Left <= nums1Right:
# Valid partition found
if total % 2 == 1:
return float(max(nums1Left, nums2Left))
else:
a = max(nums1Left, nums2Left)
b = min(nums1Right, nums2Right)
return (a + b) / 2.0
elif nums1Left > nums2Right:
right = i - 1 # too many from nums1, shrink
else:
left = i + 1 # too few from nums1, grow
return 0.0 # unreachable if inputs are valid sorted arrays
struct Solution;
impl Solution {
fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
// Always binary search on the smaller array
if nums1.len() > nums2.len() {
return Solution::find_median_sorted_arrays(nums2, nums1);
}
let (n, m) = (nums1.len() as i32, nums2.len() as i32);
let (mut left, mut right) = (0, n); // number of elements taken from nums1 into left half
let total = n + m;
let half_left = (total + 1) / 2; // size of left half (handles odd/even uniformly)
while left <= right {
let i = left + (right - left) / 2; // elements taken from nums1
let j = half_left - i; // elements taken from nums2
// Sentinels for out-of-range boundaries
let nums1_left = if i == 0 { i32::MIN } else { nums1[(i - 1) as usize] };
let nums1_right = if i == n { i32::MAX } else { nums1[i as usize] };
let nums2_left = if j == 0 { i32::MIN } else { nums2[(j - 1) as usize] };
let nums2_right = if j == m { i32::MAX } else { nums2[j as usize] };
if nums1_left <= nums2_right && nums2_left <= nums1_right {
// Valid partition found
if total % 2 == 1 {
return nums1_left.max(nums2_left) as f64;
} else {
let a = nums1_left.max(nums2_left);
let b = nums1_right.min(nums2_right);
return (a as f64 + b as f64) / 2.0;
}
} else if nums1_left > nums2_right {
right = i - 1; // too many from nums1, shrink
} else {
left = i + 1; // too few from nums1, grow
}
}
0.0 // unreachable if inputs are valid sorted arrays
}
}