[数据结构与算法]4.寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

思路

有点难的题，用到划分的思想，重点是找到一种划分使得:

1. num1中的分割线左<num2中的分割线右；
2. num2中的分割线左<num1中的分割线右。

根据题解，只考虑移动一个数组中的分割线， 用二分查找移动分割线，另一个数组中的分割线位置根据前者的位置计算得出。

注意

1 数组相关的极端情况

这里看到两个数组，考虑：

1. 某一个数组为空时怎么办？
2. 一个数组整体都位于分割线的一端怎么办？

由于这里要考虑分割线1在nums1的首位左边的情况，分割线1在nums1的末位右边的情况，同时还要考虑分割线2在nums2的首位左边的情况，分割线2在nums2的末位右边的情况，因此写起来if语句非常繁琐，还易出错，可以用这种方法：

n1_s=mid>=0?nums1[mid]:INT_MIN;
n1_b=mid<n1-1?nums1[mid+1]:INT_MAX;
n2_s=other>=0?nums2[other]:INT_MIN;
n2_b=other<n2-1?nums2[other+1]:INT_MAX;

2 二分查找注意事项

凡是用到二分查找，考虑退出条件：有没有还没找到就提前退出的情况？

例如本题中，

1. 退出条件如果是left<=right，有没有可能在这个数组中，出现了right<left，还没改变mid指针位置就退出了循环。
2. 先想到这一可能，再往情况上套想会不会发生，会出现right<left可能是因为本轮之前mid=left，发现mid还应该往左移，所以right=mid-1，然后退出了循环，然而其实这时的mid并没有想希望的那样左移，因此mid位置错误。
3. 想到了这一点，再寻思有没有可能出现上一种情况的前提条件，也就是mid=left，但发现mid还应该往左移，正常的二分查找中mid一定在left右边，right左边，是不会出现这种情况的。所以要考虑这道题的特殊性以及数组端点这种极端情况，这道题找的是分割线，所以可能出现分隔线在0号位左边的情况，因此mid可能会需要移动到-1的位置，出现如上情况。
4. 倒推知道，可能出现1中担心的情况，因此需要额外处理1：例如在right<left时，先让mid=right，再判断是否退出。

代码

class Solution {
private:
    int k=0;
public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size(),n2=nums2.size();
        if(n1>n2){
            return findMedianSortedArrays(nums2, nums1);
        }
        int left=0,right=n1-1;
        int mid;
        k=(n1+n2+1)/2;
        int n1Little=INT_MIN,n1Large=INT_MAX,n2Little=INT_MIN,n2Large=INT_MAX;
        while(true){
            if(left>right){
                mid=right;
            }
            else
                mid=(left+right)/2;
            int other=k-(mid+1)-1;
            n1Little=mid>=0?nums1[mid]:INT_MIN;
            n1Large=mid<n1-1?nums1[mid+1]:INT_MAX;
            n2Little=other>=0?nums2[other]:INT_MIN;
            n2Large=other<n2-1?nums2[other+1]:INT_MAX;
            if(n2Large<n1Little){
                right=mid-1;
            }
            else if(n1Large<n2Little){
                left=mid+1;
            }
            else{
                break;
            }
        }

        if((n1+n2)%2){
            return (double)max(n1Little,n2Little);
        }
        else{
            return ((double)max(n1Little,n2Little)+(double)min(n2Large,n1Large))/2;
        }  
          
    }
};