Answered

Bonjour, besoin d'aide nsi
Dichotomie:
Soit TAB = [0 ; 2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 16 ; 18 ; 20 ; 22] un tableau d'entiers.
On utilise un algorithme de recherche dichotomique pour chercher si le nombre 11 est
présent dans le tableau.
a. Quels sont les sous-tableaux qui sont parcourus lors de cette recherche ?
b. Même question avec le nombre 20.

Sagot :

CAYLUS

Réponse :

Bonjour,

Explications :

#on suppose que  min(table)<=x<max(table)

def dicho(x,table):

  a = 0

  b = len(table)-1

  m = (a+b)//2

  while a < b :

     print ("a=",a,"m=",m,"b=",b)

     if table[m] == x:

        return True

     elif table[m] > x :

        b = m-1

     else :

        a = m+1

     m = (a+b)//2

  return False

 

TAB = [0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22]  

print (dicho(11,TAB))

print (dicho(20,TAB))

"""

a= 0 m= 5 b= 11

a= 6 m= 8 b= 11

a= 6 m= 6 b= 7

False

a= 0 m= 5 b= 11

a= 6 m= 8 b= 11

a= 9 m= 10 b= 11

True

"""