from random import *

# Recherche dichotomique de manière itérative

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>
    """

    position = -1
    gauche = 0
    droite = len(liste)-1

    while gauche <= droite:
        milieu = (gauche+droite)//2

        if elt == liste[milieu]:
            position = milieu
            break

        else:
            if elt < liste[milieu]:
                droite = milieu -1
            else:
                gauche = milieu + 1
            
    return position


### 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")