Advertisement
1sairandhri

median of sorted arrays

Apr 1st, 2020
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.95 KB | None | 0 0
  1. def findMedianSortedArrays(self, A, B):
  2.     l = len(A) + len(B)
  3.     if l % 2 == 1:
  4.         return self.kth(A, B, l // 2)
  5.     else:
  6.         return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.  
  7.    
  8. def kth(self, a, b, k):
  9.     if not a:
  10.         return b[k]
  11.     if not b:
  12.         return a[k]
  13.     ia, ib = len(a) // 2 , len(b) // 2
  14.     ma, mb = a[ia], b[ib]
  15.    
  16.     # when k is bigger than the sum of a and b's median indices
  17.     if ia + ib < k:
  18.         # if a's median is bigger than b's, b's first half doesn't include k
  19.         if ma > mb:
  20.             return self.kth(a, b[ib + 1:], k - ib - 1)
  21.         else:
  22.             return self.kth(a[ia + 1:], b, k - ia - 1)
  23.     # when k is smaller than the sum of a and b's indices
  24.     else:
  25.         # if a's median is bigger than b's, a's second half doesn't include k
  26.         if ma > mb:
  27.             return self.kth(a[:ia], b, k)
  28.         else:
  29.             return self.kth(a, b[:ib], k)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement