import numpy as np
import matplotlib.pyplot as plt

######### Q 1


def recherche_naive(tab, x):
    for elt in tab:
        if elt == x:
            return True
    return False

#Dans le pire cas, il y a n comparaisons lorsque tab est de taille n
#####################☺

#########Q3
def recherche_dicho(tab, x):
    n = len(tab)
    d = 0
    f = n - 1
    while d <= f:
        m = (d + f) //2
        if x == tab[m]:
            return True
        elif x < tab[m]:
            f = m - 1
        else :
            d = m + 1
    return False

t = [2, 3, 6, 8, 11, 12]
assert recherche_dicho([], 5) == False
assert recherche_dicho(t, 2) == True
assert recherche_dicho(t, 12) == True

#1 itération
assert recherche_dicho(t, 6) == True
#max d'itération
assert recherche_dicho(t, 7) == False

############# Q 4
def nb_iteration_max(tab):
    n = len(tab)
    d = 0
    f = n - 1
    x = tab[f] + 1 #x est à droite du tableau
    nb = 0
    while d <= f:
        nb = nb + 1
        m = (d + f) //2
        if x < tab[m]:
            f = m - 1
        else :
            d = m + 1
    return nb
assert nb_iteration_max([2, 3, 6, 8, 11, 12, 13, 14]) == 4


####



### Q5

def tableau_trie(n):
    return [k for k in range(n)]


######## Q6
taille = [2 ** i for i in range(16)]


### Q7
nbIt = np.zeros(16)
for i in range(16):
    nbIt[i] = nb_iteration_max( tableau_trie(taille[i]) )
    
############ Q8 et Q9
plt.scatter(taille, nbIt)
plt.plot(taille, np.log(taille))
plt.plot(taille, 2*np.log(taille))



####Q10
def indice(tab, x):
    n = len(tab)
    d = 0
    f = n 
    while d < f:
        m = (d + f) //2
        if x == tab[m]:
            return m
        elif x < tab[m]:
            f = m - 1
        else :
            d = m + 1
    return d


t = [2, 3, 6, 8, 11, 12]

assert indice(t, 1) == 0
assert indice(t, 13) == 6
assert indice(t, 12) == 5
assert indice(t, 5) == 2