Suchprogramm (C++)

BasStard

Guten Morgen zusammen!

Leider hab ich mich zum freiwilligen Referat gemeldet. Das hat aber leider nix mit meiner Ausbildung zu tun. Selten blöd, wenn man sich erst meldet, bevor man das Thema kennt. Dicker Fehler!

Jetzt hab ich da ein paar kleine Probleme!

Hab mir schon einige C++ Bücher ausgeliehen und auch gelesen; bzw. versucht zu lesen und zu verstehen. Ist aber nen bissle schwer, wenn man 0 anfängt.

Ich hoffe hier gibts ein paar Leute, die mir bei meiner Thematik etwas helfen könnten.

Folgende Frage:

Ich soll die einzelnen Schritte angeben, die ein Suchprogramm bei der binär Suche nach dem Wert 42 ausführen muss!
Gegeben: In einem Feld mit int-Werten seien die folgenden Werte ab Index 0 gespeichert: 23, 12, 17, 3, 34, 31, 83, 42, 25

Da ich noch nie programmiert habe, fällt es mir schwer nur anhand der theorie Bücher was auf die Beine zu stellen. Hoffe mir kann einer helfen!

Besten Dank im Voraus!

Vellas

Hi!

Guck mal, erster Treffer bei google:
http://www.wachtler.de/informatik_2/node58.html
Da gibt es auch eine C++-Version. Sieht auch so aus, als wäre dort alles gut dokumentiert.

Ansonsten kannst du es ja mal mit Google: C++ Binäre Suche versuchen.

Greetz

CStoll

BasStard schrieb:

Leider hab ich mich zum freiwilligen Referat gemeldet. Das hat aber leider nix mit meiner Ausbildung zu tun. Selten blöd, wenn man sich erst meldet, bevor man das Thema kennt. Dicker Fehler!

Gut erkannt
Und jetzt kommen wir zu deinem Hauptproblem: Ohne zumindest rudimentäre Kenntnisse in der Programmierung wirst du vermutlich auch mit unseren Erklärungen nicht viel anfangen können. Aber ich versuche es trotzdem mal:

Die binäre Suche funktioniert etwa so, wie du im Telefonbuch einen Namen suchst (nur etwas konsequenter durchgezogen). Die Suche geht zunächst einmal davon aus, daß die Eingabedaten sortiert vorliegen (also müsstest du das angegebene Array erstmal sortieren, bevor du darin suchen kannst). Dann nimmst du dir jeweils das mittlere Element des gegebenen Bereiches und vergleichst es mit dem Suchwert - ist das Element größer als der Suchwert, schmeißt du den gesamten Bereich rechts davon weg (weil die auch alle größer sind), ist es kleiner, schmießt du den Bereich links weg, bevor du mit dem entsprechend kleineren Bereich wieder von vorne anfängst. Das geht so lange, bis entweder das betrachtete Element gleich dem Suchwert ist (dann hast du den Wert gefunden) oder du einen leeren Bereich in der Hand hältst (dann war der Suchwert nicht vorhanden).