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

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

思路

有点难的问题，用划分的思想，重点是找一个划分:

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

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

注意

1 与数组相关的极端情况

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

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

因为这里要考虑分割线1nums1左侧第一条情况，分割线1在nums在1的末位右侧，还应考虑分割线2nums2的第一个左边，分割线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]: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;         }                  } };