Python Binäre Suche

  2. How-To's
  3. Python How-To's
  4. Python Binäre Suche
Harshit Jindal 30 Januar 2023
Python Python Algorithm
  1. Binärer Suchalgorithmus
  2. Python-Programm für binäre Suche
Python Binäre Suche
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
Autor: 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

Verwandter Artikel - Python Algorithm