C#: Wie kann ich die binäre Suche am besten schreiben?
Hallo alle zusammen.
Ich habe eine Frage bezüglich dieses Quellcodes hier.
static void Main(string[] args)
{
int[] Reihe = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // Anlegen eines Arrays
int max; // Bestimmung der Variablen
int min;
int mid;
int Zahl;
bool erfolgreich = false;
min = 0;
max = Reihe[9];
foreach(int write in Reihe) // Ausgabe der vorhandenen Zahlen
{
Console.WriteLine(write);
}
Console.WriteLine("Geben Sie Ihre Zahl ein, damit wir überprüfen können, ob diese im System hinterlegt ist."); // Abfrage der gesuchten Zahl
Zahl = Convert.ToInt32(Console.ReadLine());
while (min <= max) // Mittelwert ermitteln
{
mid = (min + max) / 2;
mid = Reihe[mid];
if (mid < Zahl) // Wenn gesuchte Zahl größer als der Mittelwert, befindet sich der Wert in der rechten Hälfte
{
min = mid + 1;
}
if (mid > Zahl) // Wenn gesuchte Zahl kleiner als der Mittewert, befindet sich der Wert in der linken Hälfte
{
max = mid - 1;
}
if (mid == Zahl) // Wenn gesuchte Zahl gleich dem Mittelwert = Suche erfolgreich
{
erfolgreich = true;
break;
}
}
if (erfolgreich == true) // Ausgabe, ob die Zahl gefunden wurde oder nicht
{
Console.WriteLine("Ihre Zahl, die Sie eingegeben haben, ist im System hinterlegt.");
Console.ReadLine();
}
else
{
Console.WriteLine("Ihre Zahl, die Sie eingegeben haben, ist NICHT im System hinterlegt.");
Console.ReadLine();
}
Und zwar möchte ich ein Programm schreiben, welches eine binäre Suche in einem Programm durchführt. Aber ich bekomme es nicht genau hin.
Die Funktion soll sein, dass, wenn ich das Programm starte eine Abfrage kommt, wo man dann eine gewünschte Zahl eingibt und danach Bescheid bekommt, ob diese in der Reihe vorhanden ist.
Wenn ich dort eine falsche Zahl eingebe, die nicht in der Reihe ist, kommt eine Fehlermeldung. Außerdem klappt das Programm wirklich nur, wenn im Array {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } steht. Aber hier hätte ich auch gerne andere Werte.
Danke im Voraus.
MfG
2 Antworten
error
Nutze für die Grenzen nicht die Werte der Array-Elemente, sondern die Array-Indizes.
int min = 0;
int max = Reihe.Length - 1;
Teile des Weiteren auf:
mid = (min + max) / 2;
int midValue = Reihe[mid];
Die Variable mid speichert den aktuellen mittleren Index. Mit midValue wiederum wird verglichen. Statt if-if-if wäre ein if-else if-Konstrukt passender, denn nur maximal eine Möglichkeit kann eintreten.
Werden für die Berechnung der Grenzen denn inzwischen die Indizes verwendet?
Ich weiß gerade nicht genau was du meinst ich habe es aber bisher so:
static void Main(string[] args)
{
int[] Reihe = new int[] { 1, 2, 13, 24, 35, 46, 57, 68,79,99 }; //Anlegen eines Arrays
int max; //Bestimmung der Variablen
int min;
int mid;
int Zahl;
bool erfolgreich = false;
min = 0;
max = Reihe.Length;
foreach(int write in Reihe) //Ausgabe der vorhandenen Zahlen
{
Console.WriteLine(write);
}
Console.WriteLine("Geben Sie Ihre Zahl ein damit wir überprüfen können ob diese im System hinterlegt ist"); //Abfrage der gesuchten Zahl
Zahl = Convert.ToInt32(Console.ReadLine());
while (min <= max) //Mittelwert ermitteln
{
mid = (min + max) / 2;
int midValue= Reihe[mid];
if (mid < Zahl) //Wenn gesuchte Zahl größer als der Mittelwert befindet sich der Wert in der rechten Hälfte
{
min = mid + 1;
}
if (mid > Zahl) //Wenn gesuchte Zahl kleiner als der Mittewert befindet sich der Wert in der linken Hälfte
{
max = mid - 1;
}
if (mid == Zahl) //Wenn gesuchte ZAhl gleich dem Mittelwert = Suche erfolgreich
{
erfolgreich = true;
break;
}
}
if (erfolgreich == true) //Ausgabe ob die Zahl gefunden Wurde oder nicht
{
Console.WriteLine("Ihre Zahl die Sie eingegeben haben ist im System hinterlegt");
Console.ReadLine();
}
else
{
Console.WriteLine("Ihre Zahl die Sie eingegeben haben ist NICHT im System hinterlegt ");
Console.ReadLine();
}
Tut mir leid wenn ich etwas offensiv bin aber hast du herausgefunden warum es nicht die Zahlen im Array akzeptiert aber dafür die Zahlen wie lang das Array ist? Oder wenn es möglich ist mir die Lösung als Quellcode einstellen?
MFG
Es gibt zwei Fehler.
1) Der maximale Index muss um 1 kleiner sein, als die Länge der Liste, andernfalls kann der Index überlaufen werden.
int max = Reihe.Length - 1;
Ich werde das in meiner obigen Antwort noch korrigieren.
2) Du hast meinen letzten Abschnitt ignoriert. In deinem Code vergleichst du den Index mit dem gesuchten Wert. Doch für diesen Vergleich ist ja midValue eingeführt worden.
Zudem nochmal Hinweise zur Code-Qualität:
- Der ausgewürfelte Mittelwert kann nur größer/kleiner/gleich der gesuchten Zahl sein. Nicht alles gleichzeitig. Trotzdem stolpert dein Programmfluss in jedem Fall durch alle drei if-Köpfe, obwohl dies nur im schlechtesten Fall notwendig wäre.
Viel besser:
if (midValue < Zahl)
{
// ...
}
else if (midValue > Zahl)
{
// ...
}
else if (midValue == Zahl)
{
// ...
}
- Die Benamung der Variablen ist noch suboptimal. Deutsch und Englisch sind gemischt (meine eingeführte midValue-Variable hat da nicht den Anfang gemacht, sondern mid) und ebenso die Groß-/Kleinschreibung. Die Namen lokaler Variablen beginnen nach Konvention stets mit einem Kleinbuchstaben. Zahl und Reihe gehören dazu. Sie stellen keine Klassen, Namespaces, Properties, o.ä. dar.
- Verbinde wo nur möglich Deklaration und Definition. So sparst du an Zeilen ein.
int max = Reihe.Length - 1;
int min = 0;
Vielen Dank für die schnelle Antwort.
Ich habe trotzdem noch ein Problem und zwar wenn ich jetzt im meinem Array andere Zahlen habe z.b
int[] Reihe = new int[] { 1, 2, 13, 24, 35, 46, 57, 68,79,99 };
Und bei der Abfrage einer dieser Zahlen eingebe kommt eine Fehlermeldung an dieser Stelle:
int midValue= Reihe[mid];
Aber wenn ich eine Zahl zwischen 0-9 eingebe steht da das diese Zahl stimmt.
Also irgendwie nimmt das Programm nur die Zahlen wie lang das Array ist.
Wenn mein Array z.b 15 Werte hat sind Zahlen 0-15 richtig.
Ich hoffe du kannst mir da weiterhelfen
Nochmals Vielen Dank
MFG