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

#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    Solution(){}
    ~Solution(){}
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        //两个数组的总长度
        int len=nums1.size()+nums2.size();
        if (len%2==1)
        {
            //总长度为奇数，则为中间数为中位数
            return getKValue(nums1,nums2,len/2+1);
        }else{
            //总长度为偶数，则中间两数的平均数为中位数
            return (getKValue(nums1,nums2,len/2)+getKValue(nums1,nums2,len/2+1))/2.0;
        }
    }
    
    int getKValue(vector<int>&num1,vector<int>&num2,int k){
        int len1=num1.size();
        int len2=num2.size();
        int index1=0,index2=0;
        while (true)
        {   
            //处理边界
            if(index1==len1){
                return num2[index2+k-1];
            }
            if(index2==len2){
                return num1[index1+k-1];
            }
            if (k==1)
            {
                return min(num1[index1],num2[index2]);
            }
            //当前num1和num2起始的位置 
            int newIndex1=min(index1+k/2-1,len1-1);
            int newIndex2=min(index2+k/2-1,len2-1);
            int pov1=num1[newIndex1];
            int pov2=num2[newIndex2];
            //当前index前面的值可以丢弃，并更新index的位置，k也随着变小
            if (pov1<=pov2)
            {
                k=k-(newIndex1-index1+1);
                index1=newIndex1+1;
            }else{
                k=k-(newIndex2-index2+1);
                index2=newIndex2+1;
            }
        }
    }
};

int main(){
    Solution s;
    vector<int> nums1={1,2}; 
    vector<int> nums2={3,4}; 
    cout<<s.findMedianSortedArrays(nums1,nums2);
}