Binäre Suche in Ringpuffer/ Ringspeicher
-
Hallo,
hat von Euch schon mal jemand eine binäre Suche über einen Ringpuffer/ Ringspeicher implementiert?
Wenn ja, wäre ich für einen Tipp dankbar.Gruß
Leo
-
Du verstehst unter binärer Suche eine Suche, die nicht sequentiell durch den Puffer wandert, sondern die Schrittweite, mit dem der aktuelle Suchindex erhöht oder vermindert wird, so lange um 2 vermindert wird, bis der richtige Treffer erzielt wurde?
Und unter einem Ringpuffer verstehst Du einen Speicher, der keinen Anfang und kein Ende hat?Also für einen Ringpuffer habe ich noch keine binäre Suche gemacht. Ist im Prinzip aber auch nicht viel schwieriger als bei einem "einfachen" linearen Speicher. Du mußt beim Ermitteln des nächsten aktuellen Index halt nur immer aufpassen, daß Du am physischen Ende des Ringpuffers wieder auf den physischen Anfang zurückspringst (bzw. umgekehrt natürlich auch). Das setzt beim Ermitteln des aktuellen Suchindex eine etwas kompliziertere Logik voraus. Ebenso bei der Ermittlung der Anzahl der Elemente im Ringpuffer, da ja Schreib- und Lesezeiger unterschiedliche Positionen haben können. Aber wo siehst Du die Schwierigkeit?
Noch eine Frage: ist der Ringpuffer tatsächlich so groß, daß sich eine binäre Suche wirklich lohnt?