复习：找出两个正序数组的中位数

思路
  题目要求对数时间复杂度，所以立马反应出用二分法；从宏观的角度，本题二分法的思路就是，通过每一次，丢弃k/2个数，直到最后让你比较两个正序数组里的最小数，也就是k==1的情况；
  <mark>然后就是细节细节再细节的边界问题；如果，在丢弃数据的过程中，有一个数组遍历完了，那么问题变成在一个数组里面寻找某一个数；</mark>

代码分析

class Solution {
   
public:
    double getKthNumInTwoSortedArrays(vector<int>& nums1, vector<int>& nums2,int k){
   
        //假设两个数组各贡献k/2，然后每一次可以k/2，直到最终让你找出两个数中的最小数
        //可能存在的边界条件，k还没有等于1，其中一个数组已经到达了末尾，那么就相当于在一个数组里面取一个数
        int ai=0,bi=0;
        int len1=nums1.size();
        int len2=nums2.size();

        while(true){
   
            if(ai==nums1.size())
                return nums2[bi+k-1];
            if(bi==nums2.size())
                return nums1[ai+k-1]; 
            if(k==1)    
                return std::min(nums1[ai],nums2[bi]);
            int new_ai=std::min(ai+k/2-1,len1-1);
            int new_bi=std::min(bi+k/2-1,len2-1);

            int pivot_a=nums1[new_ai];
            int pivot_b=nums2[new_bi];
            if(pivot_a<=pivot_b){
   //可以丢弃nums1中的前k/2个元素
                k-=new_ai-ai+1;
                ai=new_ai+1;
            }else {
   
                k-=new_bi-bi+1;
                bi=new_bi+1;
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
   
        //时间复杂度O(log(m+n))立马想到二分法
        //可以把题目升华为找到两个升序数组里的第k个数
        int len=nums1.size()+nums2.size();
        if(len%2!=0)
            return getKthNumInTwoSortedArrays(nums1,nums2,len/2+1);
        else 
            return (getKthNumInTwoSortedArrays(nums1,nums2,len/2)+getKthNumInTwoSortedArrays(nums1,nums2,len/2+1))/2;
    }
};

细节之处见真章

 if(k==1)    
                return std::min(nums1[ai],nums2[bi]);
                //return std::min(nums1[0],nums2[0]);

此处 ，最开始写成了下面一行，竟也没有察觉到；由于在不断的丢弃数据的过程中，最终可能就变成了在两个数组中，找出最小值；由于我们“丢弃”不是真的把数据丢掉了，只是首下标的偏移而已！！！