# es_en_llista

## solució 1: recursiva lineal final

def es_en_llista_1(llista, elem):
    if len(llista) == 0:
        return False
    else:
        m = len(llista)//2
        if llista[m] == elem:
            return True
        elif llista[m] > elem:
            return es_en_llista_1(llista[:m], elem)
        else:
            return es_en_llista_1(llista[m+1:], elem)

## solució 3: immersió d'eficiència amb range

def es_en_llista_3(llista, elem):
    return es_en_llista_3_r(llista, elem, range(len(llista)))

def es_en_llista_3_r(llista, elem, llesca):
    if len(llesca) == 0:
        return False
    else:
        m = len(llesca)//2
        if llista[llesca[m]] == elem:
            return True
        elif llista[llesca[m]] > elem:
            return es_en_llista_3_r(llista, elem, llesca[:m])
        else:
            return es_en_llista_3_r(llista, elem, llesca[m+1:])

## solució 2: immersió d'eficiència amb índexs

def es_en_llista_2(llista, elem):
    return es_en_llista_2_r(llista, elem, 0, len(llista)-1)
        
def es_en_llista_2_r(llista, elem, i, j):
    if j < i:
        return False
    else:
        m = (i+j)//2
        if llista[m] == elem:
            return True
        elif llista[m] > elem:
            return es_en_llista_2_r(llista, elem, i, m-1)
        else:
            return es_en_llista_2_r(llista, elem, m+1, j)

## tria la solució

#es_en_llista = es_en_llista_1
#es_en_llista = es_en_llista_2
es_en_llista = es_en_llista_3


# index_llista

## solució 1: immersió amb índexs

def index_llista_1(llista, elem):
    return index_llista_1_r(llista, elem, 0, len(llista)-1)
        
def index_llista_1_r(llista, elem, i, j):
    if j < i:
        return -1
    else:
        m = (i+j)//2
        if llista[m] == elem:
            return m
        elif llista[m] > elem:
            return index_llista_1_r(llista, elem, i, m-1)
        else:
            return index_llista_1_r(llista, elem, m+1, j)

## solució 2: immersió amb range

def index_llista_2(llista, elem):
    return index_llista_2_r(llista, elem, range(len(llista)))

def index_llista_2_r(llista, elem, llesca):
    if len(llesca) == 0:
        return -1
    else:
        m = len(llesca)//2
        if llista[llesca[m]] == elem:
            return llesca[m]
        elif llista[llesca[m]] > elem:
            return index_llista_2_r(llista, elem, llesca[:m])
        else:
            return index_llista_2_r(llista, elem, llesca[m+1:])

## tria la solució

#index_llista = index_llista_1
index_llista = index_llista_2