# DIU 2019 - Bloc 2 algorithmiques
# Cette liste de programmes permet d'implémenter des algorithmes de recherches dichotomiques et linéaires.

import time
from matplotlib import pyplot as plt

liste=[]
for i in range(1,10001):
    liste.append(i)
    
# fonction lineaire pour 10000 valeurs
def lineaire(nbre_secret):
    for i in range(10000):
        if liste[i]==nbre_secret:
            return "trouvé!"
        
# fonction lineaire_print pour 10000 valeurs        
def lineaire_print(nbre_secret):
    for i in range(10000):
        print("test n° ", i+1)
        if liste[i]==nbre_secret:
            return "trouvé!"

# fonction lineaire_etapes pour 10000 valeurs
def lineaire_etapes(nbre_secret):
    nb_etapes=0
    for i in range(10000):
        nb_etapes=nb_etapes+1
        if liste[i]==nbre_secret:
            return "trouvé! en ", nb_etapes, " étapes"

# fonction lineaire_time pour 10000 valeurs
def lineaire_time(nbre_secret):
    start_time = time.time()
    for i in range(10000):
        if liste[i]==nbre_secret:
            return "trouvé! en " , time.time() - start_time
        
# pour les fonctions dichotomiques, a et b désignent respectivement le début et la fin de l'intervalle
# fonction dicho pour 10000 valeurs
def dicho(nbre_secret):
    a = liste[0]      
    b=liste[9999]
    m=(a+b)//2
    while m!=nbre_secret:
        if nbre_secret<m:
            b=m
            m=(a+b)//2
        else:
            a=m
            m=((a+b)//2)+1
    return "trouvé!"

# fonction dicho_print pour 10000 valeurs
def dicho_print(nbre_secret):
    a = liste[0]
    b=liste[9999]
    m=(a+b)//2
    cpt=0
    while m!=nbre_secret:
        cpt=cpt+1
        if nbre_secret<m:
            print("test n° ", cpt, "sur intervalle de", a, "à", m)
            b=m
            m=(a+b)//2
        else:
            print("                                           test n° ", cpt, "sur intervalle de", m, "à", b)
            a=m
            m=((a+b)//2)+1
    print("test n° ",cpt+1)
    return "trouvé!"

# fonction dicho_time pour 10000 valeurs
def dicho_time(nbre_secret):
    start_time = time.time()
    a = liste[0]
    b=liste[9999]
    m=(a+b)//2
    while m!=nbre_secret:
        if nbre_secret<m:
            b=m
            m=(a+b)//2
        else:
            a=m
            m=((a+b)//2)+1
    return "trouvé! en ", time.time()-start_time

# fonction dicho_etapes pour 10000 valeurs
def dicho_etapes(nbre_secret):
    a = liste[0]
    b=liste[9999]
    m=(a+b)//2
    nb_etapes=0
    while m!=nbre_secret:
        nb_etapes=nb_etapes+1
        if nbre_secret<m:
            b=m
            m=(a+b)//2
        else:
            a=m
            m=((a+b)//2)+1
    nb_etapes=nb_etapes+1
    return "trouvé! en ", nb_etapes, "étapes"

# fonctions lineaire_tps, dicho_tps et graphes pour n valeurs
def lineaire_tps(taille,nbre_secret):
    start_time = time.time()
    n=taille
    for i in range(n):
        if liste[i]==nbre_secret:
            return time.time() - start_time
   
def dicho_tps(taille,nbre_secret):
    start_time = time.time()
    n=taille
    a = liste[0]
    b=liste[n-1]
    m=(a+b)//2
    while m!=nbre_secret:
        if nbre_secret<m:
            b=m
            m=(a+b)//2
        else:
            a=m
            m=((a+b)//2)+1
    return time.time()-start_time
   
def graphes(taille):
    global liste
    liste=[]
    for i in range(1,taille+1):
        liste.append(i)
    liste_tlin=[]
    liste_tdich=[]
    for t in range(10,taille+1,100):
        n_secret=t
        liste_tlin.append(lineaire_tps(t,n_secret))
        liste_tdich.append(dicho_tps(t,n_secret))
    plt.title("complexité : recherche linéaire vs dichotomique")
    plt.xlabel("n (taille du tableau)")
    plt.ylabel("temps d'exécution (s)")
    plt.plot(liste_tdich)
    plt.plot(liste_tlin)
    plt.show()
    return "Fini"