Recherche dichotomique en Python

Document 对象参考手册Exemples Python3

La recherche dichotomique est un algorithme de recherche permettant de trouver un élément spécifique dans un tableau trié. Le processus de recherche commence par l'élément du milieu du tableau. Si l'élément du milieu se trouve être l'élément recherché, le processus de recherche se termine. Si un élément spécifique est supérieur ou inférieur à l'élément du milieu, la recherche se poursuit dans la moitié du tableau où les éléments sont supérieurs ou inférieurs à l'élément du milieu et, comme au début, la comparaison commence par l'élément du milieu. Si le tableau devient vide à une étape donnée, cela signifie que l'élément n'est pas trouvé. Cet algorithme de recherche réduit de moitié l'intervalle de recherche à chaque comparaison.

Exemple : Récursion

# Renvoie l'indice de x dans arr, ou -1 s'il n'existe pas def binarySearch (arr, l, r, x): # Vérification de base if r >= l: mid = int(l + (r - l)/2) # L'élément est exactement à la position du milieu if arr[mid] == x: return mid # Si l'élément est plus petit que l'élément à la position du milieu, il suffit de comparer les éléments à gauche elif arr[mid] > x: return binarySearch(arr, l, mid-1, x) # Si l'élément est plus grand que l'élément à la position du milieu, il suffit de comparer les éléments à droite else: return binarySearch(arr, mid+1, r, x) else: # Non trouvé return -1 # Tableau de test arr = [ 2, 3, 4, 10, 40 ] x = 10 # Appel de fonction result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print ("L'indice de l'élément dans le tableau est %d" % result ) else: print ("L'élément n'est pas dans le tableau")

L'exécution du code ci-dessus produit la sortie suivante :

元素在数组中的索引为 3

Document 对象参考手册Exemples Python3

Autres extensions