leetcode4

gistfile1.txt

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        if(nums1.size() == 0 || nums2.size() == 0 || (nums1.size() > 1 && *nums1.begin() == *nums1.rbegin()) ||(nums2.size() > 1 && *nums2.begin() == *nums2.rbegin())){
            
        vector<int> &ref = (nums1.size() > 0 ? nums1 : nums2);
        if(nums1.size() > 0 && nums2.size() > 0){
            if (*nums1.begin() == *nums1.rbegin()){
                ref = nums2;
            }else {
                ref = nums1;
            }
        }

        int left=ref[0], right=*ref.rbegin();
        int target = ref.size()/2;
        bool even = ref.size() % 2 == 0;
        while(left<=right){
            int mi = (left+right)>>1;
            int vmi = search(ref, mi, 0, ref.size());
            if(vmi == target){
                return mi;
            }else if(even && (vmi = search(nums1, mi+0.5, 0, nums1.size()) + search(nums2, mi+0.5, 0, nums2.size()))== target){
                return mi+0.5;
            }
            else
                {
                if(vmi < target){
                    left = mi+1;
                }else{
                    right = mi -1;
                }
            }
        }
        return -999;
    }else{
        int min1 = min(nums1[0], nums2[0]);
        int max1 = max(*nums1.rbegin(), *nums2.rbegin());
        if (min1 == max1){
            return min1;
        }
        int left=min1, right=max1;
        int total = nums1.size() + nums2.size();
        int target = total /2;
        bool even = total % 2 == 0;
        while(left<=right){
            int mi = (left+right)>>1;
            int vmi = search(nums1, mi, 0, nums1.size()) + search(nums2, mi, 0, nums2.size());
            if(vmi == target){
                return mi;
            }else {
                if(even && (vmi = search(nums1, mi+0.5, 0, nums1.size()) + search(nums2, mi+0.5, 0, nums2.size()))== target){
                    return mi+0.5;
                }
                else{
                    if(vmi < target){
                        left = mi+1;
                    }else{
                        right = mi -1;
                    }
                }
            }
        }
        return -999;
    }
    }
    int search(vector<int>& A, double e, int lo,int hi){
        while(lo<hi){
            int mi = (lo+hi)>>1;
            e  <A[mi]? hi=mi : lo = mi+1;
        }
        if(--lo < 0){
        return 0;
        }
        if(A[lo] <e){
            return lo+1;
        }else {
            return lo;
        }
        
    }
};