Wieso funktioniert mein Python-Code für eine binäre Suche in einem Array nicht?
Wenn ich diesen Code auf meiner Konsole eingebe funktioniert nichts, was sehr fragwürdig ist da ich den Code schon dutzende male durchgegangen bin. Kann mir irgendjemand helfen? Die genaue Aufgabenstellung befindet sich als Bild im Anhang.
Code:
def binarySearch(arr, num):
. a = 0
. b = len(arr) - 1
. counter = 0
. while a <= b:
. m = (a + b) // 2
. if num <= arr[m]:
. b = m
. else:
. a = m + 1
. counter += 1
. if num == arr[a]:
. return counter
. else:
. return -1
mein_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
gesuchte_zahl = 8
ergebnis = binarySearch(mein_array, gesuchte_zahl)
Der Code nochmal
2 Antworten
Du hast eine Endlosschleife erzeugt, denn ein Fund wird von dir ignoriert.
Schau dir dazu die Zwischenwerte an, die bei Programmablauf erzeugt werden:
a = 0
b = 9
0 <= 9 ist wahr
m = 4
8 <= 5 ist unwahr
a = 5
5 <= 9 ist wahr
m = 7
8 <= 8 ist wahr
b = 7
5 <= 7 ist wahr
m = 6
8 <= 7 ist unwahr
a = 7
7 <= 7 ist wahr
m = 7
8 <= 8 ist wahr
b = 7
usw. ...
Bei Fund sollte die Schleife stattdessen beendet werden.
while a <= b:
counter += 1
m = (a + b) // 2
if num == arr[m]:
return counter
if num < arr[m]:
b = m
else:
a = m + 1
so wie ich das sehe, wird, wenn die zahl gefunden wird -1 von deiner funktion ausgegeben, aber bei deiner letzten if else verzweigung wird -1 dafür benutzt um zu zeigen das die zahl nicht gefunden wurde