4. Median of Two Sorted Arrays (R)

Link: https://leetcode.com/problems/median-of-two-sorted-arrays

Description: Find the median of the two sorted arrays.

Solution:

We can use a binary search to find the partition of the two arrays such that the left side of the partition has the same number of elements as the right side of the partition. We can find the partition by dividing the smaller array into two parts and then dividing the larger array into two parts such that the left side of the partition has the same number of elements as the right side of the partition. We can then check if the maximum element on the left side of the partition of the smaller array is less than or equal to the minimum element on the right side of the partition of the larger array and if the maximum element on the left side of the partition of the larger array is less than or equal to the minimum element on the right side of the partition of the smaller array. If this condition is met, we can return the median of the two arrays. If not, we can adjust the partition by moving it to the left or right side of the smaller array based on the comparison of the maximum element on the left side of the partition of the smaller array and the minimum element on the right side of the partition of the larger array.

var findMedianSortedArrays = function (nums1, nums2) {
  // Ensure nums1 is the smaller array
  if (nums1.length > nums2.length) {
    ;[nums1, nums2] = [nums2, nums1]
  }

  const m = nums1.length
  const n = nums2.length
  let left = 0
  let right = m

  while (left <= right) {
    const partitionX = Math.floor((left + right) / 2)
    const partitionY = Math.floor((m + n + 1) / 2) - partitionX

    const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1]
    const minRightX = partitionX === m ? Infinity : nums1[partitionX]

    const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1]
    const minRightY = partitionY === n ? Infinity : nums2[partitionY]

    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 0) {
        return (
          (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2
        )
      } else {
        return Math.max(maxLeftX, maxLeftY)
      }
    } else if (maxLeftX > minRightY) {
      right = partitionX - 1
    } else {
      left = partitionX + 1
    }
  }
  throw new Error('No median found')
}