kth smallest

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