La recherche dichotomique, ou recherche par dichotomie1 (en anglais : binary search), est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié.
Le principe est le suivant : comparer l’élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.
https://fr.wikipedia.org/wiki/Recherche_dichotomique#:~:text=La%20recherche%20dichotomique%2C%20ou%20recherche,%C3%A9l%C3%A9ment%20dans%20un%20tableau%20tri%C3%A9.&text=Le%20nombre%20d’it%C3%A9rations%20de,en%20la%20taille%20du%20tableau.
Etape 1
Ecrire une fonction liste_hasard(n,p) permettant de générer aléatoirement une liste de n nombres entiers différents compris entre 0 et p. On aura naturellement p>n.
Exemple :
>>> liste_hasard(10,100)
[54, 60, 46, 20, 64, 96, 39, 42, 51, 91]Etape 2
On considère une liste de nombres différents et triés.
En utilisant le principe de recherche par dichotomie, écrire une fonction permettant de déterminer si un nombre appartient à cette liste et de préciser alors son indice ou d’indiquer qu’il n’appartient pas à cette liste.
Travail à finir :
from random import randint
def liste_hasard(n,p):
liste=[]
while len(liste)<n+1 :
nbre=randint(0,p)
if not(nbre in liste):
liste.append(nbre)
liste.sort()
return liste
def dichotomie(x,liste):
l=liste.copy()
while len(liste)!=1 :
print()
print(liste)
i_milieu=int(len(liste)/2)
if x in liste[0:i_milieu]:
liste=liste[0:i_milieu]
else :
liste=liste[i_milieu:len(liste)]
return liste
liste=[i for i in range(0,100)]
print(liste)
print(dichotomie(68,liste))
Proposition de correction pour des listes rangées ou non rangées.
L’algorithme est plus efficace en coût et en rapidité pour une liste rangée.
from random import randint
def liste_hasard(n,p):
'''
n,p : entiers naturels avec n<p
return : liste de longueur n contenant des nbres entiers
différents compris entre 0 et p
>>> a=liste_hasard(10,50)
>>> a
[14, 42, 15, 1, 16, 34, 4, 37, 22, 11]
'''
liste=[]
for i in range(n):
arret=True
while arret:
x=randint(0,p)
if x in liste:
arret=True
else :
arret=False
liste.append(x)
return liste
def dichotomie_non_rangee(l,val):
'''
l : liste non rangée de nombres
val : un nombre entier
return : l'indice correspondant à val dans la liste l si val appartient à la liste et False sinon
>>> a=[32, 2, 37, 0, 45, 25, 3, 36, 8, 9]
>>> dichotomie_non_rangee(a,32)
0
>>> dichotomie_non_rangee(a,9)
9
>>> dichotomie_non_rangee(a,1)
False
>>>
'''
liste=l
min=0
max=len(liste)-1
while max-min!=1:
pivot=int((max+min)/2)
if val in liste[min:pivot]:
max=pivot
else :
min=pivot
if l[max]==val:
return max
if l[min]==val:
return min
return False
def dichotomie_rangee(l,val):
'''
l : liste rangée de nombres
val : un nombre entier
return : l'indice correspondant à val dans la liste l si val appartient à la liste et False sinon
>>> a=[32, 2, 37, 0, 45, 25, 3, 36, 8, 9]
>>> a.sort()
>>> a
[0, 2, 3, 8, 9, 25, 32, 36, 37, 45]
>>> dichotomie_rangee(a,0)
0
>>> dichotomie_rangee(a,45)
9
>>> dichotomie_rangee(a,1)
False
'''
liste=l
min=0
max=len(liste)-1
while max-min!=1:
pivot=int((max+min)/2)
if val <liste[pivot]:
max=pivot
else :
min=pivot
if liste[max]==val:
return max
if liste[min]==val:
return min
return False