2022-2023 - Class 4

Solution to problem on slide 3 (copied from last week's post):

n =len(A)
m =len(B)
if n>m:
    return self.findMedianSortedArrays(B,A) 
k =(n+m-1)//2 
l =0 
r =min(k,n)
while l<r:
     midA =(l+r)//2     
     midB =(k-midA)
     if A[midA]<B[midB]:         
        l = midA +1
     else:       
        r = midA 
     #recursion splits combined array into 4 sections: 
     # A into A[0:midA] and A[midA:n] 
     # B into B[0:midB] and B[midB:m] 
     # since the total length is n+m and midA + midB = k =(m+l)//2 then 
     # midA and midB split the two arrays in half collectively.  
     # so the median is between these 4 numbers:A[l-1],A[l],B[k-l], and B[k-l+1]  
     # 2of the smaller values could be A[l-1] and B[k-l] 
m1 =max(A[l-1] if l >0 else float(-1e6),B[k-l] if k-l >=0elsefloat(-1e6)) 
# 2 of the greator values could be A[l] and B[k-l+1] 
m2 =min(A[l]if l < n else float(1e6),B[k-l+1]if k-l+1< m elsefloat(1e6))
if(n+m)%2!=0:     #if length is odd this is the answer     
   return m1 
else:             #if length is even this is the answer     
   return(m1+m2)/2.0

Solution to problem on slide 5:

#  you can use native python to do this problem
return list(set(nums))

Solution to problem on slide 6 (HW):

# This is a standard binary search problem. you maintain a left and right bound. while the middle of the bound is to the left of the target, make the middle the left bound and if the middle is to the right of the target make the middle the right bound. Eventually you will find the target in the array or you will find the values closest to the target using this method.
l = 0
r = len(nums)-1
m = None
while l<=r:
   m = (l+r)//2
   if nums[m]==target:
       return m
   elif nums[m]>target:
       r = m-1 #you dont need to check m again (target lies between l and m-1)
   else:#nums[m]<target
       l = m+1 #you dont need to check m again (target lies between m+1 and r)
return -1

Let me know if you have any questions about the slides or code in this post or need help understanding a problem or its solution.