subject

Give two positively ordered (from small to large) arrays nums1 and nums2 of sizes m and n, respectively. Please find and return the median of these two positive arrays.

The time complexity of the algorithm should be O(log (m+n)).

Tips:
     ~~~~      nums1.length == m
     ~~~~      nums2.length == n
     ~~~~      0 <= m <= 1000
     ~~~~      0 <= n <= 1000
     ~~~~      1 <= m + n <= 2000
     ~~~~      -106 <= nums1[i], nums2[i] <= 106

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merge array = [1,2,3], median 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Interpretation: array (1,2,2) / median = 1,2,2 + 2,4

This topic is hard. I think the most difficult part is the classification of different situations and the determination of subscript boundaries.

First attempt (many vulnerabilities)

It's easy to think in the way of merging and sorting. Double pointers keep going backwards in two arrays. Search is a cycle, which is divided into three cases and processed in turn.
Circular lookup:

 while(n1 < nums1.length && n2 < nums2.length && i < (total+1)/2){//In the basic case, the condition of out circulation is (total+1)/2 - 1. At this time, the corresponding one is the one to be found
     if(nums1[n1] < nums2[n2] && nums1[n1] > min){
         n1++;
         flag = 1;
     }else if(nums1[n1] > nums2[n2] && nums2[n2] > min){
         n2++;
         flag = 2;
     }    
     i++;
 }

Situation Division: 1: I found what I was looking for

if(i >= (total+1)/2){
	//Both arrays occupy
    if(total%2 == 0){
        flag = nums1[n1]>nums2[n2]?flag:(3-flag);
        if(flag == 1){
            return (nums1[--n1] + nums2[n2])/2.0;
        }else if(flag == 2){
            return (nums1[n1] + nums2[--n2])/2.0;
        }
    }else if(flag == 1){
        return nums1[--n1]/1.0;
    }else if(flag == 2){
        return nums2[--n2]/1.0;
    }
}

Handle 2 and 3 according to the situation: nums1 or nums2 cross the boundary, and the one to be found is on one side

if(n1 >= nums1.length){//All in nums2 array
    temp = (total+1)/2 - n1 - 1;
    return (nums2[temp] + nums2[temp + (total+1)%2])/2.0;
}else if(n2 >= nums2.length){//All in nums1 array
    temp = (total+1)/2 - n2 - 1;
    return (nums1[temp] + nums1[temp + (total+1)%2])/2.0;
}

With the failure of the following example, declare this method bankrupt o(╥﹏╥) O.

Input:
[1,2]
[-1,3]
Output:
2.00000
Expected results:
1.5

The case described in the above example is that the total number is even, and two medians are required, and the two medians are exactly in an array. The first attempt was flawed.

Repair completed

The defect of the initial attempt is that when the total number is even, it is assumed that the first median is found, and the other median is the next one of this array (the other array is out of bounds) or the current subscript of another array (neither array is out of bounds).
Through the above examples, it is revealed that the situation division is problematic.
The repair is as follows, and it passes successfully:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        int n1 = 0, n2 = 0;
        int i = 0;
        int min = 0;//It can be set to any value, and the value will be assigned later

        //There are three conditions for jumping out of the loop: nums1 has found the head, nums2 has found the head, and has found what to look for
        //Set the condition as I < (total + 1) / 2: when the total number is even, directly find the smaller of the two median numbers, and then compare to get the next one
        while(n1 < nums1.length && n2 < nums2.length && i < (total+1)/2){
            if(nums1[n1] < nums2[n2]){
                min = nums1[n1];
                n1++;
            }else{
                min = nums2[n2];
                n2++;
            }
            i++;
        }

        //Found what you're looking for
        if(i >= (total+1)/2 && total%2 == 0){//The total number is even, and the next median of the two needs to be compared
            if(n2 >= nums2.length){
                return (min + nums1[n1])/2.0;
            }else if(n1 >= nums1.length){
                return (min + nums2[n2])/2.0;
            }else if(nums1[n1] < nums2[n2]){
                return (min + nums1[n1])/2.0;
            }else{
                return (min + nums2[n2])/2.0;
            }
        }else if(i >= (total+1)/2 && total%2 == 1){//Total odd number, return directly
            return (float)min;
        }

        if(n1 >= nums1.length){//nums1 found the header. It's all in nums2 array
            n2 = (total-1)/2 - n1;
            return (nums2[n2] + nums2[n2 + (total+1)%2])/2.0;
        }else if(n2 >= nums2.length){//nums2 found the header, which is in nums1 array
            n1 = (total-1)/2 - n2;
            return (nums1[n1] + nums1[n1 + (total+1)%2])/2.0;
        }

        return 0;
    }
}

New problems also appear in the repair process. be careful

1. We should deal with the situation of "finding what we want" first. It will be much easier. If you first deal with the array crossing, when colleagues meet the two conditions of crossing the boundary and finding the target, the processing situation will be a headache, and the two conditions of finding the head need to be improved in detail.
2. Determination of boundary. In the case of finding the head, re assign values to n1 and n2. At this time, we should find several examples to help determine the boundary conditions.
3. Several solution errors occur when an array is empty. After looking at the tips, there are no restrictions on this situation. Finally, it is found that there is a problem with the assignment of n1 and n2 when the array is out of bounds.
4. Parity division in the case of finding the header: n2 and n2 + (total+1)%2 point to the same element as a subscript in the case of odd number, and point to the current and next element in the case of even number. Divide all directly by 2, eliminating the separate distinction between parity and parity.

Liberate this problem and study other methods in two days. Problem solving and guidance

For the first time, it's hard to solve the hard problem. What does it mean to pull one hair and move the whole body - solving one bug leads to / finds another bug is really a state of mind.