Correction de l'exercice sur la Dichothomie

Pour cet exercice

In [4]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]

x1 = 9

x2 = 40

Question 1

In [6]:
def recherche_dichotomie(x, tableau):
    gauche = 0
    droite = len(tableau)
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == x:
            return True
        elif tableau[milieu] > x:
            droite = milieu - 1
        else:
            gauche = milieu + 1
    return False
In [7]:
recherche_dichotomie(x1, T)
Out[7]:
False
In [8]:
recherche_dichotomie(x2, T)
Out[8]:
True

Question 2 a

In [2]:
def recherche(x, tableau):
    for i in range(len(tableau)):
        if tableau[i] == x :
            return i
        if tableau[i] > x :
            return -1
    return -1
In [9]:
recherche(x1, T)
Out[9]:
-1
In [10]:
recherche(x2, T)
Out[10]:
7

Question 2 b

In [11]:
def recherche_dichotomie(x, tableau):
    gauche = 0
    droite = len(tableau)
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == x:
            return milieu
        elif tableau[milieu] > x:
            droite = milieu - 1
        else:
            gauche = milieu + 1
    return -1
In [12]:
recherche_dichotomie(x1, T)
Out[12]:
-1
In [13]:
recherche_dichotomie(x2, T)
Out[13]:
7