T2: Beispiel 2

[Hallo]

Hi, ich möchte hier mal mein Lösungsvorschlag zum 2. Beispiel des Theorie 2 vorschlagen:


Input: Ein Aufsteigensortierter Array a und ein zu suchendes Element int x.

Wohldefiniertheit: Es gibt keine Instruktionen, die auf Attribute oder Methoden == null verweisen oder zugreifen. Es gibt keine Divisionen durch 0.

Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.

Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.

Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.

Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.

Induktionsschritt: Entweder x ist größer bzw. kleiner als den Wert des Pivotposition und es wird die erste bzw. die zweite Hälfte des Arrays vernachlässigt, bzw. i wird gleich m+1 oder j wird gleich m-1 gesetzt.

Korrektheit: Dank der Variante, dass der Intervall sich ständig halbiert, erreicht der Algorithmus einer der beiden Abbruchbedingung und der Korrekte Ergebnis wird zurückgeliefert.

[Sonne34]

Vielen Dank für die Bereitstellung deiner Lösung. Ich habe sie mal mit meinen verglichen.
Anbei nun meine zusätzlichen Ideen, über Feedback würde ich mich freuen

Input: Ein Aufsteigensortierter Array a und ein zu suchendes Element int x.

Ich habe hier: Ein Array a mit ganzen Zahlen, dass aufsteigend sortiert ist, wobei a[0]+...+a[a.length-1] <= Integer.MAX_VALUE. Zudem eine ganze Zahl x, welche das gesuchte Element in a darstellt.

Wohldefiniertheit: Es gibt keine Instruktionen, die auf Attribute oder Methoden == null verweisen oder zugreifen. Es gibt keine Divisionen durch 0.

Es existieren keine Instruktionen die auf Attribute oder Methoden von null zugreifen und auch keine Division durch 0. Ein Überlauf kann aufgrund der Einschränkung des Inputs nicht passieren.

Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.

Hier habe ich: Aufgrund der Variante, wird die Abbruchbedingung i>j nach endlich vielen Schritten erreicht. Ich schätze mal das meine Aussage zu knapp ist oder?

Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.

Auch hier bin ich mir unsicher mit meiner Formulierung : m wird in jedem Aufruf echt kleiner, da entweder i größer wird, oder j kleiner wird.

Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.

Nach i>=0 Iterationen wurden die ersten i - Stellen des Arrays nach dem gesuchten Wert x durchsucht.
Kann es sein, dass du hier eig das Beispiel 3 gepostet hast? Schließlich liegt bei Beispiel zwei die iterative Version vor und nicht die rekursive?

Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.

Vor der Schleife, also nach 0 Iterationen wurden keine Stellen des Arrays durchsucht.

Liebe Grüße

[yokop]

Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.

Wenn i == j dann wird die Schleife noch ausgeführt, da die Bedingung i <= j ist. Passender ist hier wohl i > j als Abbruchbedingung.

Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.

Kann man wahrscheinlich so stehen lassen. In jeder Iteration wird entweder i = m+1 oder j = m-1 gesetzt, wobei m = (i+j)/2. Das heisst, dass sich i und j in jedem Schritt echt aufeinander zu bewegen.

Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.

Zwischen dem Intervall i bis j ? Ich würde hier schreiben, im Intervall [i,j].

Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.

Es handelt sich nicht um eine Rekursion. Sonst passt es, jedoch das mit dem Parameter m ist nicht wirklich nötig. Vielleicht könnte man noch erwähnen, dass es falls vorhanden in dem Intervall ist.

Induktionsschritt: Entweder x ist größer bzw. kleiner als den Wert des Pivotposition und es wird die erste bzw. die zweite Hälfte des Arrays vernachlässigt, bzw. i wird gleich m+1 oder j wird gleich m-1 gesetzt.

Hier fehlt wieso folgt, dass das Element dann in dem neuen Intervall seien muss. Hier habe ich folgendes geschrieben:
Nach Induktionsvoraussetzung befindet sich x, falls vorhanden in a..a[j]. Falls nun a[m] == x, mit m = (i+j)/2, dann ist das Element gefunden und die Position m wird zurückgegeben. Sei nun a[m] != x, dann muss das Element also in dem restlichen Bereich zu finden sein (falls vorhanden..). Je nachdem ob also a[m] < x oder a[m] > x, befindet sich x in a[m+1=i]...a[j] bzw. a..a[m-1=j] aufgrund der aufsteigenden Sortierung des Array. Also ist das Element auch nach einer Iteration noch im von i und j begrenzten Bereich.

[Max_S]

Die offizielle Lösung findet ihr übrigens in den Tutorien... (ich glaub das war in Tutorium 2)