def srednja_vrednost(tab):
    ''' Poišči srednjo vrednost v tabeli z liho elementi'''
    return k_ti(tab, (len(tab) + 1) // 2)

def k_ti(tab, k):
    '''vrni k-ti podatek v tabeli'''
    if len(tab) == 1:
        if k != 1: raise Exception('Napaka!')
        return tab[0]
    # razmečemo
    pivot = tab[0]
    manjsi_enaki = []
    vecji = []
    for x in tab[1:]: # prvega spustimo
        if x <= pivot:
            manjsi_enaki.append(x)
        else:
            vecji.append(x)
    # kje je
    koliko_manjsih = len(manjsi_enaki)
    if koliko_manjsih == k - 1:
        return pivot
    if koliko_manjsih >= k:
        return k_ti(manjsi_enaki, k)
    return k_ti(vecji, k - koliko_manjsih - 1)

if __name__ == '__main__':
    import random
    p3 = [10, 5, 12]
    print(srednja_vrednost(p3)) # 10
    p3 = [10, 10, 10]
    print(srednja_vrednost(p3)) # 10
    p1 = range(11)
    print(srednja_vrednost(p1)) # 5
    p2 = list(p1)
    random.shuffle(p2)
    print(srednja_vrednost(p2)) # 5
    p2 = [12, 4, 34, 1, 10]
    print(srednja_vrednost(p2)) # 5