# -*- coding: utf-8 -*-
"""
TP6 : Dichotomie - Corrigé

PCSI2 - Albert Schweitzer - Le Raincy
"""

##Q2

def recherche(L: list, e) -> bool:
    '''Renvoie True si e est dans L,
    False sinon
    '''
    for element in L:
        if e == element:#on a trouvé e
            return True
    return False

##Q3
'''
Dans le pire des cas, e n'est pas dans L et on
parcourt toute la liste en faisant un test à
chaque fois : on a donc une complexité linéaire O(n), où n = len(L).
'''

##Q4-Q5-Q6-Q7-Q8
'''
Au début, g = 0 et d = len(L)-1.
Le milieu de l'intervalle [g,d] se calcule par (g+d)/2.
Mais attention, l'indice doit être un entier, donc
m = (g+d)//2.
Si e < L[m], on prend d = m - 1.
Si e > L[m], on prend g = m + 1.
On a besoin d'une boucle while (on ne sait pas
combien d'itération on va faire), d'un if, elif, else
des variables g, d et m.
Avant de continuer, on doit vérifier si g <= d.
'''

##Q9-Q10
def recherche_dichotomique(L:list, e) -> bool:
    '''
    Renvoie True si e est dans L et False sinon.
    On utilise la dichotomie.
    Précondition : L est triée par ordre croissant.
    '''
    g, d = 0, len(L) - 1
    while g <= d:
        m = (g+d)//2
        if L[m] == e:#on a trouvé e
            return True
        elif L[m] < e:#e est à droite de m
            g = m + 1
        else:#e est à gauche
            d = m - 1
    return False

##Q11
import random as rd

def liste_alea(n:int) -> list:
    '''Renvoie une liste triée de n entiers
    aléatoires choisis entre 0 et n
    '''
    L = []
    for i in range(n):
        L.append(rd.randint(0, n))
    L.sort()
    return L

##Q12 Tests
assert recherche_dichotomique([1], 1) == True
assert recherche_dichotomique([1], 0) == False
assert recherche_dichotomique([1,2], 1) == True
assert recherche_dichotomique([1,2], 2) == True
assert recherche_dichotomique([1,2], 0) == False
L = liste_alea(100)
assert recherche_dichotomique(L, L[0]) == True
assert recherche_dichotomique(L, L[-1]) == True
assert recherche_dichotomique(L, -1) == False
L = liste_alea(101)
assert recherche_dichotomique(L, L[0]) == True
assert recherche_dichotomique(L, L[-1]) == True
assert recherche_dichotomique(L, -1) == False

##Q13
'''
Rien de particulier ?
'''

##Q14
from time import process_time
from time import time

n = 10**6
L = liste_alea(n)
debut = time()
recherche(L, -1)#-1 n'est pas dans la liste
fin = time()
print('Recherche naive : ', fin-debut)

debut = time()
recherche_dichotomique(L, -1)#-1 n'est pas dans la liste
fin = time()
print('Recherche dicho : ', fin-debut)

##Q15
'''
Après une itération, on note d' et g' les nouvelles valeurs.
On a deux cas :
- soit d' = (d+g)//2 - 1 et d' < (d+g)/2, donc
d'-g' < (d+g)/2 -g = (d-g)/2
- soit g' = (d+g)//2 + 1 et g' > (d+g)/2, donc
d'-g' < d - (d+g)/2 = (d-g)/2
'''

##Q16
'''
d-g est un variant de boucle : c'est une quantité
qui doit rester positive et qui diminue strictement
à chaque itération.
'''

##Q17
'''
On a un variant !
'''

##Q18
'''
Au maximum, on arrive à d - g < 1. On cherche k
tel que n/2**k < 1, Et on trouve n<2**k, donc
k < log(n). Ainsi, on fera au max
partie_ent(log(n)) +1 itérations avant de terminer.
La fonction a donc une complexité logarithmique.
'''

##Q19
'''
Avant de rentrer dans la boucle, g = 0, et d = n-1, donc L[0:g] et L[d+1:len(L)] sont vides.
'''

##Q20
'''
Supposons qu'au début d'une itération, e n'est ni
dans L[0:g] ni dans L[d+1:len(L)]. On note
g' et d' les nouvelles valeurs de g et d.
Il y a deux cas:
- soit d' = m - 1 et e n'est pas dans L[m:d+1]
et dans ce cas, e n'est pas dans L[0:g'] ni dans
L[d'+1:d+1] ou L[d+1:len(L)] donc pas dans L[d'+1:len(L)]
- soit g' = m + 1, on fait pareil.
'''

##Q21
'''
C'est un invariant de la boucle.
'''

##Q22
def insertion(L:list, x) -> None:
    '''Insère x au bon endroit dans la liste triée
    L. Effet de bord : modifie L
    '''
    L.append(x)#On insère brutalement
    j = len(L) - 2
    #Variant : j
    while j >= 0 and L[j] > x:#x n'est pas au bon endroit
        L[j+1] = L[j]
        j = j-1
    #En sortie : x >= L[j] ou bien j = -1
    L[j+1] = x

##Q23
def tri_insertion(L:list) -> list:
    '''Renvoie une copie triée de L
    '''
    M = []
    for e in L:
        insertion(M, e)
    return M

##Q24
'''
On note m la longueur de M.
L'appel insertion(M,e) a une complexité O(m) dans le
pire des cas, donc la complexité totale est
O(sum(m=0, len(L)) m) = O(len(L)^2)
On a une complexité quadratique.
'''