Python Binäre Suche
Harshit Jindal
30 Januar 2023
![Python Binäre Suche](/img/Python/ag-feature-image---python-binary-search.webp)
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
auf0
undhi
aufn - 1
. -
Während
lo
<hi
, setzemid
=lo + (hi - lo)/2
.- Wenn
A[mid]
==X
, haben wir das Element gefunden und geben den Indexmid
zurück. - Wenn
A[mid]
<X
, dann verwerfen wir die linke Hälfte der Elemente und setzenlo
alsmid+1
. - Wenn
A[mid]
>X
, dann verwerfen Sie die rechte Hälfte der Elemente und setzen Siehi
alsmid-1
.
- Wenn
-
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 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