Leetcode4: 寻找两个有序数组的中位数

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    //Leetcode4: 寻找两个有序数组的中位数
    int totalLen = nums1.size() + nums2.size();
    if((totalLen%2)!=0){
        //odd
        return (double)findKthElement(nums1, nums2, totalLen/2 + 1);
    }
    else{
        double n1 = (double)findKthElement(nums1, nums2, totalLen/2);
        double n2 = (double)findKthElement(nums1, nums2, totalLen/2 + 1);
        return (n1 + n2)/2;
    }
}

int findKthElement(vector<int> & nums1, vector<int> & nums2, int target){
    int m = nums1.size();
    int n = nums2.size();
    int start1 = 0;
    int start2 = 0; //the pointer is set to be zero at first
    while (true){
        cout<<"start1: "<<start1<<endl;
        cout<<"start2: "<<start2<<endl;
        cout<<"target: "<<target<<endl;
        cout<<endl;
// handle the special case first
        if(start1 >= m){
            //vector 1 out of range
            return nums2[start2 + target - 1];
        }
        
        if(start2 >= n){
            //vector 2 out of rage
            return nums1[start1 + target - 1];
          }
        if(target == 1){
            // return the smallest at the beginnig
            return min(nums1[start1],nums2[start2]);
        }
        
        // if the index is out of range, choose the element at last to compare 
        // the number of elements being expeled depends on the index
        int index1 = min(start1 + target/2 - 1, m - 1);
        int index2 = min(start2 + target/2 - 1, n - 1);
        int pivot1 = nums1[index1];
        int pivot2 = nums2[index2];
        if(pivot1 <= pivot2){
            target = target - (index1 - start1 + 1);
            start1 =  + index1 + 1;
            continue;
        }
        else{
            target = target - (index2 - start2 + 1);
            start2 = index2 + 1;
        }
        
}
}

【总体思路】
题目要求时间复杂度是log(m+n), 于是想到二分法
如果数组的总体长度N是奇数，那么中位数就是第N/2 + 1 个数
如果总体长度是偶数，那么中位数就是中间两个数求平均值
整个问题可以转换为 - > 在两个有序数组中找第K个数

首先比较两个数组中 第k/2 - 1 个数 可以帮助排除一些数据
排除小的那个数组前面k/2 - 1 个数，因为它最多前面有(k/2 - 1)*2 个数比它小，即k/2 - 2 个数比它小，所以不可能是第k个数，它和它前面的都可以排除。排除之后更新开头指针