Eine einfache binäre Suche

[Miffel (Gast)]

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?

[Sam .. (sam1994)]

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

[Karl H. (kbuchegg)]

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

[Miffel (Gast)]

@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...