Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- Read the docs of find median of two sorted array.
- '''
- from math import inf
- class Solution:
- def kthElement(self, a, b, k):
- if len(a)>len(b):
- a,b=b,a
- n1=len(a)
- n2=len(b)
- l = max(0, k - n2) # we take elements from the array1 in such a way that to get k-cut1 elements should be there in the arr2, It should not be there k-cut1 is gonna exceed the arr2 length
- r = min(k, n1)
- while l<=r:
- cut1= (l+r)//2
- cut2= k-cut1
- left_first= a[cut1-1] if cut1>0 else -inf
- left_second=b[cut2-1] if cut2>0 else -inf
- right_first=a[cut1] if cut1<n1 else inf
- right_second=b[cut2] if cut2<n2 else inf
- if left_first<=right_second and left_second<=right_first:
- return max(left_first,left_second)
- elif left_first>right_second:
- r=cut1-1
- else:
- l=cut1+1
- return -1
Advertisement
Add Comment
Please, Sign In to add comment