Median of two sorted arrays

Array Binary Search Divide and Conquer

46.0% acceptance

Jan 12, 2026

31877

3556

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)).

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    // Ensure nums1 is the smaller array for efficiency
    if nums1.len() > nums2.len() {
      return Self::find_median_sorted_arrays(nums2, nums1);
    }
    
    let m = nums1.len();
    let n = nums2.len();
    let mut low = 0;
    let mut high = m;
    
    while low <= high {
      // Partition nums1
      let partition1 = (low + high) / 2;
      // Partition nums2 such that left side has same elements as right side
      let partition2 = (m + n + 1) / 2 - partition1;
      
      // Get max elements on left side and min elements on right side
      let max_left1 = if partition1 == 0 { i32::MIN } else { nums1[partition1 - 1] };
      let min_right1 = if partition1 == m { i32::MAX } else { nums1[partition1] };
      
      let max_left2 = if partition2 == 0 { i32::MIN } else { nums2[partition2 - 1] };
      let min_right2 = if partition2 == n { i32::MAX } else { nums2[partition2] };
      
      // Check if we found the correct partition
      if max_left1 <= min_right2 && max_left2 <= min_right1 {
        // If total length is even
        if (m + n) % 2 == 0 {
          return (max_left1.max(max_left2) as f64 + min_right1.min(min_right2) as f64) / 2.0;
        } else {
          // If total length is odd
          return max_left1.max(max_left2) as f64;
        }
      } else if max_left1 > min_right2 {
        // Move partition1 to the left
        high = partition1 - 1;
      } else {
        // Move partition1 to the right
        low = partition1 + 1;
      }
    }
    
    // Should never reach here if inputs are valid
    0.0
  }
}