HOWTO · Python
Recherche dichotomique en Python
Ce didacticiel montre comment utiliser l'algorithme de Recherche dichotomique en Python.
Sur cette page
Noter
Si vous voulez comprendre la Recherche dichotomique en détail, reportez-vous à l’article algorithme de Recherche dichotomique.
Algorithme de Recherche dichotomique
Supposons que nous ayons un tableau non trié A[] contenant n éléments, et nous voulons trouver un élément X.
-
Définissez
losur0ethisurn - 1. -
Tant que
lo<hi, définissezmid=lo + (hi - lo)/2.- Si
A[mid]==X, nous avons trouvé que l’élément renvoie l’indexmid. - Si
A[mid]<X, alors supprimez la moitié gauche des éléments et définissezlosurmid+1. - Sinon, si
A[mid]>X, alors supprimez la moitié droite des éléments et définissezhicommemid-1.
- Si
-
L’élément est introuvable, renvoyez donc
-1.
Programme Python pour la Recherche dichotomique
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 1, 5]
x = 4
n = len(arr)
result = binary_search(arr, x, n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
Production:
Element is present at index 2
