def qth_smallest( m , n, q ):
if q > len( m ) + len( n ):
return None
a = 0
b = 0
while a < len( m ) and b < len( n ):
if m[a] < n[b]:
if a + b + 1 == q:
return m[a]
a += 1
else:
if a + b + 1 == q:
return n[b]
b += 1
while a < len( m ):
if a + b + 1 == q:
return m[a]
a += 1
while b < len( n ):
if a + b + 1 == q:
return n[b]
b += 1
# kth smallest in two sorted arrays: classic merge sort two fingers crossing
def kth_smallest( m , n, k ):
if k > len( m ) + len( n ):
return None
a = 0
b = 0
union_sorted = list()
while len( union_sorted ) < k and a < len( m ) and b < len( n ):
if m[a] < n[b]:
union_sorted.append( m[a] )
a += 1
else:
union_sorted.append( n[b] )
b += 1
union_sorted += m[ a: ]
union_sorted += n[ b: ]
print union_sorted
return union_sorted[ k-1 ]
# all left, all right, odd left and even right, even left and odd right, even even, odd odd
# last element in one array, first element in another array
# not found
if __name__ == '__main__':
assert None == kth_smallest( [0,1] , [2,3], 5 )
assert 2 == kth_smallest( [ 0, 1, 2 ], [ 3,4,5 ], 3 )
assert 2 == kth_smallest( [ 3,4,5 ], [ 0, 1, 2 ], 3 )
assert 4 == kth_smallest( [ 1,3], [ 2,4 ], 4 )
assert 2 == kth_smallest( [ 1,3], [ 2,4 ], 2 )
assert 9 == kth_smallest( [ 7, 8, 10 ], [ 3,9 ], 4 )
assert 10 == kth_smallest( [ 7, 8, 10 ], [ 3,9 ], 5 )
assert None == qth_smallest( [0,1] , [2,3], 5 )
assert 2 == qth_smallest( [ 0, 1, 2 ], [ 3,4,5 ], 3 )
print kth_smallest( [ 3,4,5 ], [ 0, 1, 2 ], 3 )
# TODO: binary search of both arrays simultaneously