from random import randint

def median(a, start=None, end=None):
    """find the median value of a sorted list or in a subset of it"""
    if start is None:
        start = 0
    if end is None:
        end = len(a)
    l = end-start
    if l < 1:
        raise "median value of a empty list? It make no sense"
    index = start + l/2
    if l % 2 == 0:
        return index, (a[index] + a[(index-1)]) / 2.0
    else:
        return index, float(a[index])

def median_2_lists(l1, l2):
    """find the median value of 2 sorted list"""
    iter = 0
    solution = None
    left1 = 0
    left2 = 0
    right1 = len(l1)
    right2 = len(l2)
    
    print l1[left1:right1], l2[left2:right2]
    
    while True:
        iter = iter+1
        index1, value1 = median(l1, left1, right1)
        index2, value2 = median(l2, left2, right2)
        
        minus1 = 1 if (right1-left1) % 2 == 0 else 0
        minus2 = 1 if (right2-left2) % 2 == 0 else 0
        remove_offset = max(1, min((right1-left1) / 2 - minus1, (right2-left2) / 2 - minus2))
        
        # to avoid special blocking case like [-5,5] [1,2], [5, 5] [-11, -8, 20, 21]
        # I decided to stop the algorithm and insert the 2 last items into the big list
        if right1-left1 <= 2 or right2-left2 <= 2:
            break
      
        if value1 < value2:
            left1 += remove_offset
            print "removed of left side of l1 : %d" % remove_offset
            right2 -= remove_offset
            print "removed of right side of l2 : %d" % remove_offset
        elif value1 > value2:
            left2 += remove_offset
            print "removed of left side of l2 : %d" % remove_offset
            right1 -= remove_offset
            print "removed of right side of l1 : %d" % remove_offset
        else:
            print "solution found"
            solution = value1
            break
        
        print l1[left1:right1], l2[left2:right2]
    
    if right1-left1 > right2-left2:
        big = l1
        short = l2
        left = left1
        right = right1
        i = left2
        end = right2
    else:
        big = l2
        short = l1
        left = left2
        right = right2
        i = left1
        end = right1
    
    if solution is None:
        assert 0 < end-i < 3
        # we need to insert the remaining 1 or 2 number(s) of the short list
        # into the big list at the right place. It's done in a dichotomic way
        while i < end:
            l, r = left, right
            while True:
                index, value = median(big, l, r)
                if value == short[i] or index == l or index == r:
                    if short[i] > value:
                        # here we modify the list: it's bad, I need to fix it
                        big.insert(index+1, short[i])
                    else:
                        big.insert(index, short[i])
                    i += 1
                    right += 1
                    break
                else:
                    if short[i] > value:
                        l = index
                    if short[i] < value:
                        r = index
        solution = median(big, left, right)[1]
        
    return solution, iter

def test_median_2_lists():
    print "Generating random lists"
    l1 = []
    l2 = []
    i = 0
    n = randint(5,9)
    while i<n:
        l2.append(randint(0,9))
        i += 1
    i = 0
    n = randint(5,9)
    while i<n:
        l1.append(randint(0,9))
        i += 1
    
    l1.sort()
    l2.sort()
    
    merge = list(l1)
    merge.extend(l2)
    merge.sort()
    
    control_value = median(merge)[1]
    
    print "Start algorithm"
    solution, iter = median_2_lists(l1, l2)
    print "%s iteration(s) done" % iter
    print "control value : %f" % control_value
    print "solution value : % f" % solution
    assert control_value == solution
    print "Successful!"
    

test_median_2_lists()