Binäre Suche mit zwei Werten (Intervall)



  • Hallo,
    ich habe einen (großen) Datensatz (Typ vector), in dem ich durch binäre Suche ein Intervall suchen soll, dessen untere und obere Grenze durch Benutzereingaben festgelegt wird.
    Beispiel:

    vector<double> x = { 0,1,2,4,5,6,8,9,10 };
    

    Annahme: Der Benutzer tippt 3 (untere Grenze) und 7 (obere Grenze) ein.
    Voraussetzungen wie z.B. untere Grenze < obere Grenze, keine negativen Eingaben, ... werden vorher schon überprüft.
    Bei Werten, die im Datensatz nicht vorkommen, soll jeweils der nächstkleinere Wert genommen werden. Hier soll das Lösungsintervall also 2,6 bzw. x[2],x[5] sein.
    Die Werte von x (insbesondere der erste und letzte Wert) sind alle bekannt, sind ganzzahlig (trotzdem double für weitere Berechnungen) und liegen sortiert (aufsteigend) vor (aber eben mit Lücken).

    Wie implementiere ich diese Art der binären Suche? Muss zugeben, dass ich damit noch nie gearbeitet habe. Zudem bin ich mir unsicher, wie ich das mit den zwei Werten am effektivsten machen soll: Das Verfahren für beide Werte anwenden, oder nur den ersten Wert (untere Grenze) suchen und dann um die Differenz der Werte (oG-uG) "weitergehen" und dort den Wert nehmen (bzw. ggf. den nächstkleineren). Vermute mal, dass die Suche für beide Werte besser und genauer ist.

    Danke für eure Hilfe und schönes Wochenende!


  • Mod

    Weißt du, wie du einen Wert suchst? Wenn du das hast, dann machst du das eben für zwei Werte. Du musst dir überlegen, was du machst, wenn der Suchpfad sich teilt. Offensichtlich musst du dann von dort aus jeweils einen der Werte in den beiden Gabeln suchen.

    Alternativ kannst du natürlich auch einfach 2x nach jeweils einem Wert suchen und es dir egal sein lassen, dass dies eventuell ein paar wenige Operationen zusätzlich benötigt. Durch die verminderte Codekomplexität könnte das sogar am Ende eventuell sogar schneller sein. Binäre Suche ist O(log(N)), es müssten schon extrem viele Werte sein, damit sich die Doppelsuchoptimierung wirklich lohnt.



  • Hey,

    habe es hinbekommen und erhalte nun zumindest für mein kleines Beispiel immer den passenden Wert zurück. Werde das später mal für das eigentliche Problem testen, bin aber optimistisch, dass es da dann auch funktionert.

    Zur Zeit wende ich die Suche zweimal an, einmal für den unteren und einmal für den oberen Wert.

    Datenmenge liegt später bei ca. 3000 Werten, weiß jetzt nicht ob das "viel" ist. Denke aber nicht, dass 3000 "extrem viel" ist.

    Danke für deine Antwort 🙂



  • War ich wohl zu optimistisch...

    Meine Programm sieht zur Zeit wie folgt aus:

    double bins (vector<double> &field, double lval, double rval, double val) 
    {
      if (lval > rval) return field[lval-1];
      double mid = (rval+lval)/2;
      if (field[mid] == val) return mid;
      if (val < field[mid]) return bins(field, lval, mid - 1, val);
      else return bins(field, lval + 1, rval, val);
    }
    int main(void)
    {
      double ug=3,og=7;
      vector<double> x={0,1,2,4,5,6,8,9,10};
      //double ug=30,og=70;
      //vector<double> x={0,10,20,40,50,60,80,90,100};
      double size = t.size();
      double left=t[0];
      double right=t[size-1];
      cout<<bins(x,left,right,ug)<<endl;
      cout<<bins(x,left,right,og)<<endl;
    }
    

    Für das obige Beispiel erhalte ich 2 bzw. 6 zurück, also genau das was ich suche. Wenn ich jetzt Zeile 11+12 auskommentiere und stattdessen 13+14 benutze, erhalte ich jeweils nur noch 0 bzw. 0 zurück. In size, left und right stehen in beiden Fällen die richtigen Werte. Warum funktioniert es nicht beim 2. Beispiel, was übersehe ich bzw. mache ich falsch?



  • Vectorindex als double? Benutze size_t oder direkt Iteratoren.
    Ansonsten: benutze einen Debugger.


  • Mod

    Du hast die ganze binäre Suche komplett falsch verstanden. Du musst auf den Indizes arbeiten, nicht auf dem Inhalt. Im ersten Beispiel funktioniert das zufällig, da dort der Inhalt identisch mit dem Feldindex ist.

    Nur so zur Info: Binäre Suche gibt es auch fertig in der Standardbibliothek in verschiedenen Ausführungen. std::binary_search, std::lower_bound, std::upper_bound und std::equal_range. Du musst das nicht alles selber machen. Mit equal_Range und einer cleveren Vergleichsfunktion sollte man sogar direkt dein Problem lösen können.



  • Hab mich nochmal intensiver damit befasst und bin die Funktion komplett neu angegangen, jetzt klappts auch. Danke für eure Ratschläge 🙂


Log in to reply