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.
T2: Beispiel 2
Moderator: Algorithmen und Datenstrukturen
Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Re: T2: Beispiel 2
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
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?
Liebe Grüße
Anbei nun meine zusätzlichen Ideen, über Feedback würde ich mich freuen

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.Hallo hat geschrieben:
Input: Ein Aufsteigensortierter Array a und ein zu suchendes Element int x.
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.Hallo hat geschrieben: Wohldefiniertheit: Es gibt keine Instruktionen, die auf Attribute oder Methoden == null verweisen oder zugreifen. Es gibt keine Divisionen durch 0.
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?Hallo hat geschrieben: Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.

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.Hallo hat geschrieben: Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.
Nach i>=0 Iterationen wurden die ersten i - Stellen des Arrays nach dem gesuchten Wert x durchsucht.Hallo hat geschrieben: Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.
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?
Vor der Schleife, also nach 0 Iterationen wurden keine Stellen des Arrays durchsucht.Hallo hat geschrieben: 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.
Liebe Grüße
Re: T2: Beispiel 2
Wenn i == j dann wird die Schleife noch ausgeführt, da die Bedingung i <= j ist. Passender ist hier wohl i > j als Abbruchbedingung.Hallo hat geschrieben: Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.
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.Hallo hat geschrieben: Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.
Zwischen dem Intervall i bis j ? Ich würde hier schreiben, im Intervall [i,j].Hallo hat geschrieben: Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.
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.Hallo hat geschrieben: 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.
Hier fehlt wieso folgt, dass das Element dann in dem neuen Intervall seien muss. Hier habe ich folgendes geschrieben:Hallo hat geschrieben: 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.
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.
Re: T2: Beispiel 2
Die offizielle Lösung findet ihr übrigens in den Tutorien... (ich glaub das war in Tutorium 2) 
