Let’s begin with the title:

At first, when you see log of m plus n, you immediately think of dichotomy, yes, but in this case, you have two arrays, and the sum of two arrays is odd and even. What do you do? What is the case of dichotomy? How cent? That’s what we have to think about.

What is the median?

First, to reinforce the concept of median, there are n sorted numbers.

  • If n is odd, the median is the (n+1)/2 number, the middle number.

  • If n is even, the median is the arithmetic average of the NTH / 2nd number and the NTH /2 + 1 number.

Array length: odd and even

Set the total length to n, find the (n+1)/2 number, and then find the (n+2)/2 number (note: the index values are rounded down). Then, take the average of the two numbers, which is the final median. This covers both odd and even numbers.

Three, encounter what situation carry on dichotomy? How cent?

So to go back to the beginning of the problem, we want to find a number in a particular position, so think about how we can exclude numbers that are definitely not in that position.

For example, the two arrays are [1, 2, 4, 6, 8], [5, 7, 9,11]. The total length is 9, and the median is number 5. One array is ok, but in the case of two arrays, let’s get number 5 in a more subtle way:

  • Step1: round down 5/2 to get 2, compare the second number of the two arrays, corresponding to 2 and 7, obviously the former is smaller than the latter, so now directly remove the first 2 numbers of the first array, because they are 100% in front of the median.

  • Step2: So, now that we have identified the first two numbers, we are going to ask for the third of all the following numbers. So we do what we did before, 3/2, we rounded it down to 1, and we compare the first number of the two arrays, 4 and 5, and the first number is smaller than the second, and we just throw out the first number of the first array, because it’s 100% in front of the median, so we don’t have to worry about it.

  • Step3: OK, now that we have identified the first three numbers, we are going to ask for the second number in all the following numbers. In accordance with the above approach, we eliminate 5.

  • Step4: Now that the first four numbers are determined, what is required is the first number of all the following numbers, directly compare the first number of the current two arrays, 6 < 7, we take 6. Done!

To generalize the problem is to take the KTH number, compare the KTH / 2nd number in two arrays, and if the number is small, remove all the first K /2 elements of the array, and keep repeating until k is 1 or one of the arrays is empty.

What if k/2 is larger than one of the arrays?

In this case, we just take the element at the end of the array.

5. JS code display

The code is as follows:

// find the KTH element
const findKMax = (num1, start1, end1, num2, start2, end2, k) = > {
    let len1 = end1 - start1 + 1;
    let len2 = end2 - start2 + 1;
    Num1 = num2; num1 = num2; num1 = num2
    if (len1 > len2)
        return findKMax(num2, start2, end2, num1, start1, end1, k);
    if (len1 == 0) return num2[start2 + k - 1];

    if (k == 1) return Math.min(num1[start1], num2[start2]);
    / / | 0 this operation to take down the whole
    If k/2 is larger than one of the arrays, take the last element of the array
    let i = start1 + Math.min(len1, k / 2 | 0) - 1;
    let j = start2 + Math.min(len2, k / 2 | 0) - 1;

    if (num1[i] > num2[j])
        // The j-start2 + 1 element has been removed
        return findKMax(num1, start1, end1, num2, j + 1, end2, k - (j - start2 + 1));
    else
        // The i-start1 + 1 element has been removed
        return findKMax(num1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
}
// The core function
const findMedianSortedArrays = (nums1, nums2) = > {
    let m = nums1.length;
    let n = nums2.length;
    // round down
    let left = (m + n + 1) / 2 | 0;
    let right = (m + n + 2) / 2 | 0;
    
    // Handles the case where the total length of the array is odd and even
    return (findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, left) +
        findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, right)) * 0.5;
}
Copy the code

AC successfully!