from random import *

# Recherche dichotomique de manière récursive

def RechercheDicho(liste, elt):
    """
    RechercheDicho(list liste, int elt) -> int
    Retourne la position de l'entier <elt> dans <liste>
    triée et -1 si <elt> ne se trouve pas dans <liste>
    """

    return DichoRec(liste, elt, 0, len(liste)-1)

def DichoRec(liste, elt, gauche, droite):
    """
    DichoRec(list liste, int elt, int gauche, int droite) -> int
    Retourne la position de l'entier <elt> dans <liste> triée entre les
    indices <gauche> et <droite> et -1 si <elt> ne s'y trouve pas
    """

    if gauche > droite:
        return -1
    else:
        milieu = (gauche+droite)//2
        
        if liste[milieu] == elt:
            return milieu
        else:
            if elt < liste[milieu]:
                return DichoRec(liste, elt, gauche, milieu-1)
            else:
                return DichoRec(liste, elt, milieu+1, droite)

### Programme test ###

borne = 100000
n = int(input("Nombre d'éléments de la liste: "))
liste = []
for i in range(n):
    liste.append(randint(0, borne))

liste.sort()

print("La liste à traiter est: ", liste, "\n")

elt = int(input("Elément à rechercher dans la liste: "))
pos = RechercheDicho(liste, elt)
if pos != -1:
    print("L'élément", elt, "se trouve dans la liste à la position", pos)
else:
    print("L'élément", elt, "est absent de la liste")