#include <algorithm>
using namespace std;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double res;
        if(nums1.size()==0&&nums2.size()==0)
            return 0;
        if(nums1.size() == 0){
            int size = nums2.size();
            return double((nums2[(size-1)/2] + nums2[size/2]))/2;
        }
        if(nums2.size() == 0){
            int size = nums1.size();
            return double((nums1[(size-1)/2] + nums1[size/2]))/2;
        }
        int i1 = -1, i2 = -1;
        int next = 0, pre = 0;
        int mid = (nums1.size() + nums2.size())/2;
        for(int i = 0; i <= mid; i++){
            if(i1+1 >= nums1.size()){
                i2++;
            }
            else if(i2+1 >= nums2.size()){
                i1++;
            }
            else if(nums1[i1+1] <= nums2[i2+1]){
                i1++;
            }
            else
                i2++;
            if(i == mid-1){
                if(i1 == -1){
                    pre = nums2[i2];
                }
                else if(i2 == -1){
                    pre = nums1[i1];
                }
                else{
                    pre = max(nums1[i1],nums2[i2]);
                }
            }
            if(i == mid){
                if(i1 == -1){
                    next = nums2[i2];
                }
                else if(i2 == -1){
                    next = nums1[i1];
                }
                else{
                    next = max(nums1[i1],nums2[i2]);
                }
            }
        }
        if((nums1.size() + nums2.size())%2 == 0){
            res = double((next + pre))/2;
        }
        else{
            res = next;
        }
        return res;
    }
};