mikrocontroller.net

Forum: PC-Programmierung Eine einfache binäre Suche


Autor: Miffel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallöchen!
Ich versuche hier gerade eine einfache binäre Suche (in C#) zu 
implementieren. Leider will es nicht funktionieren...

Die Situation: ich habe eine Liste mit Messwerten (Paare aus Wert & 
Zeitstempel). Nun möchte ich zu einem gegeben Zeitpunkt den 
entsprechenden Messwert finden (ein Messwert gilt immer bis zum 
nächsten).

Hier mein Code:
double GetValueAtTime( double t )
{
  // Start binary search at the middle
  int searchPos = mSamples.Count / 2;
  int searchStep = mSamples.Count / 4;

  while (searchStep > 0)
  {
    // Jump to the right
    if (t > mSamples[searchPos + 1].Timestamp)
      searchPos += searchStep;
      
    // Jump to the left
    else if (t < mSamples[searchPos].Timestamp)
      searchPos -= searchStep;
      
    // We have found the value
    else
      break;

    searchStep /= 2;
  }//end while

  return mSamples[searchPos].Value;
}

Leider bekomme ich ich ständig falsche Werte. Ich vermute mal dass das 
daran liegt, dass die Anzahl der Messwerte nicht immer eine 2er Potenz 
ist?
Oder mache ich generell etwas falsch?

Autor: Sam .. (sam1994)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
dafür nimmt man ein Directory<int,int>
Willst du es allerdings durchzählen sollte man vielleicht eher eine 
SortedLinkedList nehmen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Miffel schrieb:

> Ich versuche hier gerade eine einfache binäre Suche (in C#) zu
> implementieren. Leider will es nicht funktionieren...

Sowas gibt es zwar sicherlich schon auch fertig, aber es ist löblich das 
du Basisalgorithmen lernen willst.


> Leider bekomme ich ich ständig falsche Werte. Ich vermute mal dass das
> daran liegt, dass die Anzahl der Messwerte nicht immer eine 2er Potenz
> ist?
> Oder mache ich generell etwas falsch?

Binäre Suche sieht so einfach aus, ist es aber nicht. Das Problem 
besteht darin, dass bei einer ungeraden Anzahl Elemente im Suchraum, man 
höllisch aufpassen muss, wo die Hälfte liegt und dass man dann das 
Intervall richtig neu aufteilt.


Du musst lernen dir selbst zu helfen und zu debuggen.
Und ein Weg und bei weitem nicht der schlechteste, ist es, sich an 
strategischen Stellen strategisch wichtige Variablen ausgeben zu lassen. 
In C# steht dir ohnehin ein ausgezeichneter Weg über das Developer 
Studio und dessen Output-Fenster zur Verfügung, in das man leicht Werte 
ausgeben kann.

http://support.microsoft.com/kb/815788

Also lass dir hier jeweils beim Durchgang durch den Anfang der 
Suchschleife die Variablen ausgeben
  while (searchStep > 0)
  {

>>>>   hier ist interessant: welche Werte haben searchPos und searchStep

Und dann wird dieser Mitschrieb studiert und daraus Schlüsse gezogen

> Oder mache ich generell etwas falsch?
IMHO ja.
Beim Binären suchen hat man ein Intervall, das man durch Startindex und 
Endindex definiert und nicht durch Startindex und Größe. Wird nämlich 
ein Intervall in 2 aufgeteilt und entschieden in welchem davon 
weitergesucht werden muss, dann hat dieses neue Intervall nicht 
unbedingt eine neue Größe von step / 2

Autor: Miffel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Samuel:
Die Dictionary Klasse kannte ich noch gar nicht. Kann man die denn auch 
in meinem Fall benutzen? Denn die Werte, nach denen ich suche stehen ja 
nicht explizit im Speicher.
Wenn ich z.B. zwei Werte habe:

Wert 1:  4
Zeitstempel 1: 0

Wert 2: 9
Zeitstempel: 10

Dann soll meine Suche für ALLE Zeiten 0 < t < 10 den Wert 4, für alle 
Zeiten t >= 10 den Wert 9 zurückgeben...


@KHB:
Danke für die ausführliche Antwort! Da werde ich mich wohl nochmal etwas 
hinein-vertiefen müssen...

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.