Recherche dichotomique en Python

  2. HowTo
  3. Mode d'emploi Python
  4. Recherche dichotomique en Python
Harshit Jindal 3 janvier 2023
Python Python Algorithm
  1. Algorithme de Recherche dichotomique
  2. Programme Python pour la Recherche dichotomique
Recherche dichotomique en Python
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 lo sur 0 et hi sur n - 1.
  • Tant que lo < hi, définissez mid = lo + (hi - lo)/2.
    • Si A[mid] == X, nous avons trouvé que l’élément renvoie l’index mid.
    • Si A[mid] <X, alors supprimez la moitié gauche des éléments et définissez lo sur mid+1.
    • Sinon, si A[mid]> X, alors supprimez la moitié droite des éléments et définissez hi comme mid-1.
  • 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
Auteur: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - Python Algorithm