C++ Binary Search solution using C++ best practices.


  • 0
    G
    class Solution {
    public:   
        using citer=vector<int>::const_iterator;
        
        double findMedian(citer b1, citer e1, citer b2, citer e2,int k){
            
            if(b1 == e1){
                return *(b2 + k - 1);
            }
            
            if(b2 == e2){
                return *(b1 + k - 1);
            }
            
            if(k <= 1){
                return min(*b1,*b2);
            }    
            
            int med1 = distance(b1,e1)/2, med2 = distance(b2,e2)/2;
            
            if(*(b1 + med1) >= *(b2 + med2)){
                if(med1 + med2 + 1 >= k){
                    return findMedian(b1,b1 + med1,b2,e2,k);
                }
                
                return findMedian(b1,e1, b2 + med2 + 1, e2, k - med2 - 1);
            }
            
            if(med1 + med2 + 1 >= k){
                return findMedian(b1,e1,b2,b2 + med2,k);
            }
            
            return findMedian(b1 + med1 + 1,e1,b2,e2,k - med1 - 1);
        }
        
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            
            size_t size = nums1.size() + nums2.size();
            
            if(size % 2){
                return findMedian(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),size/2 + 1);
            }
        
            double res1 = findMedian(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),size/2 + 1);
            double res2 = findMedian(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),size/2);        
            return (res1 + res2)/2;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.