# recherche par dichotomie
# type: ignore
def dichotomie(L,n,x):
    if n==1:
        if x==L[0]:
            return 1
        else:
            return 0
    m=n//2
    if x<=L[m-1]:
        return dichotomie(L[0:m],m,x)
    else:
        return dichotomie(L[m:n],n-m,x)

# recherche linéaire
def recherche_lineaire(L,n,x):
    s=0
    for i in range(n):
        if x==L[i]:
            s=1
    return s    
        

from random import *
from time import *
n=int(input("Taille de la liste:"))
L=sample(range(-n,n+1),n)
L=sorted(L)
x=randint(-n,n)
if n<=100:
    print("Liste L:",L)
print("Nombre x:",x)
t0=time()
s1=dichotomie(L,n,x)
t1=time()-t0
t0=time()
s2=recherche_lineaire(L,n,x)
t2=time()-t0
if s1==1:
    print("x appartient à L")
else:
    print("x n'appartient pas à L")
print("Temps dichotomie:",t1,"(Réponse obtenue:",s1,")")
print("Temps recherche linéaire:",t2,"(Réponse obtenue:",s2,")")