Skip to content

Instantly share code, notes, and snippets.

@ferdbold
Last active August 29, 2015 14:15
Show Gist options
  • Save ferdbold/82ea9f3da532f72cdd07 to your computer and use it in GitHub Desktop.
Save ferdbold/82ea9f3da532f72cdd07 to your computer and use it in GitHub Desktop.
Median value of two same-length sorted lists
# Returns the two median values of two same-length sorted lists
# Algorithm complexity: O(lg n), n being the length of the lists
# Usage: mediane.py [firstlist] [secondlist]
# Input lists as integers separated by spaces (wrap list in quotemarks to input it as one command line argument)
import math, sys
def mediane(X, Y):
n = len(X)
if n == 2:
T = X + Y
del(T[T.index(min(T))])
del(T[T.index(max(T))])
return T
else:
pivot = math.ceil((n-1)/2)
if X[pivot] < Y[pivot]:
X = X[math.floor((n-1)/2):]
Y = Y[:math.floor(n/2)+1]
else:
X = X[:math.floor(n/2)+1]
Y = Y[math.floor((n-1)/2):]
return mediane(X, Y)
def main(argv):
X = argv[0].split(" ")
Y = argv[1].split(" ")
for i in range(len(X)):
X[i] = int(X[i])
Y[i] = int(Y[i])
print (mediane(X, Y))
if __name__ == "__main__":
main(sys.argv[1:])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment