import random
import time

def recherche_dichotomique(t, element):
    gauche = 0           # Borne gauche de la recherche
    droite = len(t)-1    # Borne de droite
    while gauche <= droite:
        milieu = (gauche + droite)//2
        if element > t[milieu]:
            gauche = milieu + 1
        elif element < t[milieu]:
            droite = milieu - 1
        else:
            return True
    return False

def recherche_sequentielle(t, element):
    """Fonction qui renvoie True si la valeur donnée en 2° argument est bien dans
       le tableau donné en premier argument et False sinon"""
    for item in t:
        if item == element:
            return True
    return False

def arrondi(x):
    return float('%.5g' % x)    # Arrondi x à 5 chiffres significatifs

def tableau_aleatoire(taille, mini, maxi):
    t = [0]*taille
    for i in range(taille):
        t[i] = random.randint(mini,maxi)
    return t

def evalue_fonction(fonction, texte, trie = False):
    N_MIN = 10
    N_MAX = 1000000
    MULTIPLE_N = 10   # On augmente N de ce facteur à chaque itération
    NB_RECHERCHES = 3

    n = N_MIN
    val_min = 0
    while n <= N_MAX:
        duree = 0
        for _ in range(NB_RECHERCHES):
            val_max = n*5
            t = tableau_aleatoire(n,val_min,val_max)
            if trie:   # Si on a mis l'argument "trie" à True
                t.sort()    # Alors il faut trier la liste
            debut = time.perf_counter()
            fonction(t,random.randint(val_min,val_max))
            fin = time.perf_counter()
            duree += fin-debut
        print("Recherche", texte, "pour n =",n,":",arrondi(duree/NB_RECHERCHES),"s")
        n *= MULTIPLE_N

evalue_fonction(recherche_dichotomique, "dichotomique", trie=True)
evalue_fonction(recherche_sequentielle, "séquentielle")