| k/2 | k/4 | k/8 | ...


  • 0
    Y
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.Length > nums2.Length)
            return FindMedianSortedArrays(nums2, nums1);
             
         int len1 = nums1.Length;
         int len2 = nums2.Length;
         int k = (len1 + len2) / 2;
         int i = -1;
         int j = -1;
         while( k > 0 )
         {
             int half = k / 2;
             half = half > 0 ? half : 1;
             k -= half;
             
             int n1 = (i + half) >= len1 ? int.MaxValue : nums1[i+half];
             int n2 = nums2[j + half];
             
             if( n1 > n2 )
                 j += half;
             else
                 i += half;
         }
         
         int left = Math.Max( i==-1? int.MinValue : nums1[i], j==-1? int.MinValue : nums2[j]);
         int right = Math.Min( (i+1) >= len1 ? int.MaxValue : nums1[i+1], (j+1) >= len2 ? int.MaxValue : nums2[j+1]);
         if( (len1 + len2) % 2 == 0)
         {  
             return (left + right) / 2f;
         }
         else
         {
             return right;
         }
    }

Log in to reply
 

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