Binäre Suche Struktogramm?
In Informatik müssen wir zu einer Binären Suche ein Struktogramm erstellen(Aufgabenstellung siehe Bild1). Ich habe schon einen Ansatz(Bild2), der ist glaube ich aber noch nicht ausführlich genug.
Könnte mir da jemand weiterhelfen und sagen, was noch fehlt?
Danke im Voraus!
2 Antworten
Die Abfolge deiner Anweisungen ist nicht richtig. Denn mit welchem Wert soll die zu suchende Zahl im ersten Durchlauf verglichen werden? Ebenso wird der Algorithmus nicht merken, ob es bereits einen Fund gab, da du immer nur unterteilst, ohne zu stoppen.
Ein iterativer Algorithmus könnte so aussehen:
haystack = [ 1, 2, 3, 4, 5 ]
needle = 4
min = 0
max = countElements(haystack)
while max >= min:
pivot = floor((max + min) / 2)
if haystack[pivot] == needle:
print(pivot)
break
else if haystack[pivot] < needle:
min = pivot + 1
else:
max = pivot - 1
Statt die Differenz der beiden Grenzen zu berechnen, würde ich sie nur miteinander vergleichen. Das ist schneller und einfacher.
Dann sollte zuerst das Ankerelement (pivot) berechnet werden. Dabei sollte darauf geachtet werden, dass dieser Wert als Index verwendet wird. Und Indizes rechnen stets in Einerschritten. Angenommen, du hast eine Menge von vier Elementen und rechnest dazu also:
(0 + 3) / 2 = 1.5
Heraus kommt kein gültiger Index. Das Ergebnis muss also auf irgendeine Weise gerundet werden.
Der Kern des Algorithmus liegt dann in den Vergleichen. Es gibt wie schon geschrieben drei Fälle, die eintreten können, nicht nur zwei.
- Der gesuchte Wert entspricht dem Wert am berechneten Index
- Der gesuchte Wert ist größer als der Wert am berechneten Index
- Der gesuchte Wert ist kleiner als der Wert am berechneten Index
Je nachdem kann die Schleife entweder beendet werden oder die zu durchsuchende Menge wird verkleinert.
Was du außerdem noch berücksichtigen musst: Laut Aufgabe soll das Programm (bzw. die Operation, um den Begriff aus der Aufgabenstellung zu verwenden) ein konkretes Ergebnis liefern. Mein Snippet berücksichtigt bisher auch nur den Erfolgsfall.
- Bei Fund muss das Programm die Position des Elements ausgeben. Anschließend muss es beendet werden.
- Bei keinem Fund muss das Programm (nach der Schleife) den Wert -1 ausgeben.
Ich sehe mehrere Probleme. Die Abbruchbedingugn der Schleife, Du brichst bei max-min=1 ab, bei einem Element angekommen bedeutet aber, daß max=min ist.
Dann fehlt die Festlegung von Testzahl.
Üblich wäre ja folgendes:
Bestimme die Mitte des Arrays. Ist der Wert die gesuchte Zahl, gebe Position zurück. Ist gesuchte Zahl kleiner, setze obere Grenze auf Mitte(-1) andernfalls untere auf Mitte(+1). (Überlege dir genau, ob Du mit Mitte ersetzt, oder dem Nachbarn und welches Problem hier auftreten kann).