Runtime Error (takes to long) with binary Search Code.

[Rsclub22]

Deutsch

Moin ich habe ein "kleines" Problem. Ich bin Informatikstudent und dachte mir einfach mal so (aus Spaß) diese Programmiersprache zu verwenden. Dies klappte auch alles relativ gut. Bis wir dann eine binäre Suche implementieren sollten. Eigentlich sollte in dem darauffolgendem Code kein Logik-Fehler vorhanden sein, aber vielleicht bin auch nur ich einfach blöd. Egal. Der KDDP endet auf jeden fall mit "Das Programm hat die Frist überschritten". Der Code ist hierbei folgender:

Binde "Duden/Ausgabe" ein.
Binde "Duden/Listen" ein.

[Array erstellen]
Die Zahlen Liste liste1 ist eine Liste, die aus 156, 204, 242, 403, 409, 455, 654, 704, 1000 besteht.

[Funktion für Suchen...]
Die Funktion binäreSuche mit den Parametern liste und gesuchtesElement vom Typ Zahlen Liste und Zahl, gibt eine  Zahl zurück, macht:
    Die Zahl high ist (die Länge von liste).
    Die Zahl low ist 0.
    Solange low kleiner als, oder high ist, mache:
        [ Schleifen Körper ]
        Die Zahl mid ist (low plus (high minus low) durch 2) als Zahl.
        Wenn gesuchtesElement gleich (liste an der Stelle mid) ist, dann:
            Gib mid zurück.
        Wenn aber gesuchtesElement kleiner als (liste an der Stelle mid) ist, dann:
            Die Zahl high ist mid minus 1.
        Sonst:
            Die Zahl low ist mid plus 1.
    Gib -1 zurück.
Und kann so benutzt werden:
    "Suche binär in <liste> nach <gesuchtesElement>"

Die Zahl a ist (Suche binär in liste1 nach 704).

Schreibe die Zahl a.

English

Hi, I have a "small" problem. I'm a computer science student and thought I'd just use this programming language for fun. Everything was working pretty well until we were asked to implement a binary search. There shouldn't be any logical errors in the following code, but maybe it's just me being dumb. Anyway, the KDDP ends with "Das Programm hat die Frist überschritten". Here is the code:

Binde "Duden/Ausgabe" ein.
Binde "Duden/Listen" ein.

[Create Array]
Die Zahlen Liste liste1 ist eine Liste, die aus 156, 204, 242, 403, 409, 455, 654, 704, 1000 besteht.

[Function for Searching]
Die Funktion binäreSuche mit den Parametern liste und gesuchtesElement vom Typ Zahlen Liste und Zahl, gibt eine  Zahl zurück, macht:
    Die Zahl high ist (die Länge von liste).
    Die Zahl low ist 0.
    Solange low kleiner als, oder high ist, mache:
        [ while ]
        Die Zahl mid ist (low plus (high minus low) durch 2) als Zahl.
        Wenn gesuchtesElement gleich (liste an der Stelle mid) ist, dann:
            Gib mid zurück.
        Wenn aber gesuchtesElement kleiner als (liste an der Stelle mid) ist, dann:
            Die Zahl high ist mid minus 1.
        Sonst:
            Die Zahl low ist mid plus 1.
    Gib -1 zurück.
Und kann so benutzt werden:
    "Suche binär in <liste> nach <gesuchtesElement>"

Die Zahl a ist (Suche binär in liste1 nach 704).

Schreibe die Zahl a.

[bafto]

Ich schaue es mir heute Abend mal genauer an, aber 2 Vermutungen hätte ich:

• low sollte wahrscheinlich bei 1 und nicht 0 starten (in DDP starten Listen bei 1)

• Die Berechnung von mid kommt mir komisch vor. Probier vielleicht mal

  Die Zahl mid ist ((low plus high) durch 2) als Zahl.

[bafto]

Ich schaue es mir heute Abend mal genauer an, aber 2 Vermutungen hätte ich:

• low sollte wahrscheinlich bei 1 und nicht 0 starten (in DDP starten Listen bei 1)

• Die Berechnung von mid kommt mir komisch vor. Probier vielleicht mal ``` Die Zahl mid ist ((low plus high) durch 2) als Zahl.

[bafto]

btw, binäre Suche ist eine gute Idee für ein Beispielprogramm. Wenn es funktioniert können wir es in die Beispiele mit aufnehmen :)

[bafto]

Und das offensichtlichste hab ich natürlich vergessen: Du erstellst in den Wenn-Anweisungen immer neue lokale Variablen und updatest nie die, die du benutzt. Es müsste heißen:

Speichere mid plus 1 in low.

Und das gleiche bei high.

[Rsclub22]

Jo, das hat funktioniert, ich hatte vergessen, dass das in der ddp mit 1 beginnt. Angepasst würde das jetzt so aussehen:

Binde "Duden/Ausgabe" ein.
Binde "Duden/Listen" ein.

[Array erstellen]
Die Zahlen Liste liste1 ist eine Liste, die aus 156, 204, 242, 403, 409, 455, 654, 704, 1000 besteht.

[Funktion für Suchen...]
Die Funktion binäreSuche mit den Parametern liste und gesuchtesElement vom Typ Zahlen Liste und Zahl, gibt eine  Zahl zurück, macht:
    Die Zahl high ist (die Länge von liste).
    Die Zahl low ist 1.
    Solange low kleiner als, oder high ist, mache:
        [ Schleifen Körper ]
        Die Zahl mid ist ((low plus high) durch 2) als Zahl.
        Wenn gesuchtesElement gleich (liste an der Stelle mid) ist, dann:
            Gib mid zurück.
        Wenn aber gesuchtesElement kleiner als (liste an der Stelle mid) ist, dann:
            Speichere mid minus 1 in high.
        Sonst:
            Speichere mid plus 1 in low.
    Gib -1 zurück.
Und kann so benutzt werden:
    "Suche binär in <liste> nach <gesuchtesElement>"

Die Zahl a ist (Suche binär in liste1 nach 4).

Schreibe die Zahl a.

Dies funktioniert auch soweit