def find_median(L):
    n = len(L)
    k = n//2
    if n%2 == 0:
        return (kthValue(L, k) + kthValue(L, k-1))/2
    else:
        return kthValue(L, k)

def kthValue(L, k):
    assert(len(L) > 0)
    if len(L) == 1:
        assert(k == 0)
        return L[0]
    else:
        smaller, pivot, greater = partition(L)
        if len(smaller) >= k + 1:
            return kthValue(smaller, k)
        elif len(smaller) == k:
            return pivot
        else:
            return kthValue(greater, k - len(smaller) - 1)

def partition(L):
    pivot = L[0]
    L = L[1:]
    smaller = [ v for v in L if v <= pivot ]
    greater = [ v for v in L if v > pivot ]
    return smaller, pivot, greater

def test_find_median():
    test_cases = [
        ([1, 2, 3, 4, 5], 3),
        ([1, 2, 3, 4], 2.5),
        ([1], 1),
        ([1, 3, 2], 2),
        ([5, 2, 3, 1, 4], 3),
        ([-1, -2, -3, -4], -2.5),
        ([-1, 2, -3, 4], 0.5),
#        ([7, 8, 9, 1, 2, 3], 5.5),
#        ([7, 8, 9, 1, 2, 3, 4], 4.5),
        ([3, 3, 3, 3], 3),
        ([3, 3, 4, 4], 3.5),
        (list(range(100)), 49.5),
    ]

    for lst, expected in test_cases:
        result = find_median(lst)
        assert result == expected, f"Failed for list {lst}. Expected {expected}, but got {result}."

    print("All test cases passed.")

test_find_median()