HOWTO · Python

Python Binäre Suche

Dieses Tutorial demonstriert, wie man den Binärsuchalgorithmus in Python verwendet.

Von Harshit JindalVeröffentlicht 2021-03-07Aktualisiert 2023-01-30
Auf dieser Seite
Hinweis
Wenn Sie die Binäre Suche im Detail verstehen wollen, lesen Sie den Artikel Binärer Suchalgorithmus.

Binärer Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein Element X finden.

  • Setzen Sie lo auf 0 und hi auf n - 1.
  • Während lo < hi, setze mid = lo + (hi - lo)/2.
    • Wenn A[mid] == X , haben wir das Element gefunden und geben den Index mid zurück.
    • Wenn A[mid] < X , dann verwerfen wir die linke Hälfte der Elemente und setzen lo als mid+1.
    • Wenn A[mid] > X, dann verwerfen Sie die rechte Hälfte der Elemente und setzen Sie hi als mid-1.
  • Element wird nicht gefunden, also -1 zurückgeben.

Python-Programm für binäre Suche

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))

Ausgabe:

Element is present at index 2

Über den Autor

Harshit Jindal

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.

Autorenprofil ansehen
LinkedIn