Description

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.

---

🔗 Une explication plus détaillée, en français !

---

Intuition

The problem is to find the median of two sorted arrays. The intuition behind the solution is to use a binary search approach to efficiently partition the two arrays such that the left half of the combined array has the same number of elements as the right half. By ensuring that the maximum value on the left side is less than or equal to the minimum value on the right side, we can determine the median.

Approach

1. Ensure the first array is shorter: To optimize the binary search, we ensure that the first array is the shorter one. This reduces the number of iterations needed.

2. Calculate total Length and middle index: The total length of the combined arrays is calculated, and the middle index is determined. This helps in partitioning the arrays.

3. Binary search for correct partition: We perform a binary search on the shorter array to find the correct partition indices. The goal is to find partitions such that the maximum value on the left side of both arrays is less than or equal to the minimum value on the right side.

4. Determine maximum and minimum values: For each partition, we determine the maximum values on the left side and the minimum values on the right side of both arrays.

5. Check partition validity: If the partitions are correct (meaning the maximum value on the left is less than or equal to the minimum value on the right), we calculate the median based on whether the total number of elements is even or odd.

6. Adjust search range: If the partitions are not correct, we adjust the binary search range based on the comparison of the maximum and minimum values.

Complexity

• Time complexity: The time complexity of this approach is O(log(min(n,m))), where n and m are the lengths of the two arrays. This is because we perform a binary search on the shorter array.

• Space complexity: The space complexity is O(1), as we are using a constant amount of extra space regardless of the input size.

This solution efficiently finds the median of two sorted arrays by leveraging the properties of binary search and partitioning.

Code

function findMedianSortedArrays(first: number[], second: number[]): number {
    // Ensure first is the shorter array for more efficient binary search:
    if (first.length > second.length) {
        [first, second] = [second, first];
    }

    // Calculate the total length of the combined arrays:
    const total = first.length + second.length;

    // Determine the middle index for the combined arrays:
    const middle = Math.floor((total + 1) / 2);

    // Initialize binary search pointers:
    let left = 0;
    let right = first.length;

    // Perform binary search to find the correct partition:
    while (left <= right) {
        // Calculate partition indices:
        const half = Math.floor((left + right) / 2);
        const partitions = {
            left: half,
            right: middle - half
        };

        // Determine the maximum values on the left side of each partition:
        const max = {
            left: (partitions.left === 0) ? -Infinity : first[partitions.left - 1],
            right: (partitions.right === 0) ? -Infinity : second[partitions.right - 1]
        };

        // Determine the minimum values on the right side of each partition:
        const min = {
            left: (partitions.left === first.length) ? Infinity : first[partitions.left],
            right: (partitions.right === second.length) ? Infinity : second[partitions.right]
        };

        // Check if the partitions are correct:
        if (max.left <= min.right && max.right <= min.left) {
            // Calculate the median based on the total number of elements:
            if (total % 2 === 0) {
                return (Math.max(max.left, max.right) + Math.min(min.left, min.right)) / 2;
            } else {
                return Math.max(max.left, max.right);
            }
        } else if (max.left > min.right) {
            // Adjust the binary search range:
            right = partitions.left - 1;
        } else {
            left = partitions.left + 1;
        }
    }

    // This should not be reached for valid inputs:
    return 0;
}