Communication Complexity Median in O(log(n)*log(n))

alice.py

import scipy.stats
import numpy as np
n = 200

s = scipy.stats.randint.rvs(0, n, size = 2)

X = scipy.stats.randint.rvs(0, n, size = s[0] * 2 + 1)
Y = scipy.stats.randint.rvs(0, n, size = s[1] * 2)

i = 1
j = n
alice_len = len(X)
bob_len = len(Y)

while True:
    k = np.floor((i + j) / 2)

    a = len(np.where(X < k)[0])
    b = len(np.where(Y < k)[0])

    #print "i = {}, k = {}, j = {}\na = {}, b = {}, a' = {}, b' = {}".format(i, k, j, a, b, alice_len - a, bob_len - b)

    if a + b > alice_len - a + bob_len - b:
        j = k
    else:
        i = k

    if np.abs(i - j) <= 1:
        break

m = np.median(np.append(X, Y))
print len(X), len(Y), i, m, i == m