Bereich in sortierter Liste finden

Hallo!

Ich möchte in einer sortierter Liste einen bestimmten Bereich suchen.

Also beispielsweise möchte ich den Bereich finden, der den Wert C hat, sprich: ich möchte den Anfangsindex und den Endindex haben.

AAAAAAAAAAAABBBBBBCCCCCCCCCCCCCCCCCDDDDDEEFFFFFFFFFFF
                  ^               ^
                  |               |

Die primitivste Varianten, nämlich binär nach einem passenden Element zu suchen und dann nach vorne und hinten linear bis zum Ende des Bereichs weiterzusuchen ist leider zu langsam, da die Bereiche recht groß sein können.

Vorschläge zum Lösen des Problems?

SeppJ

dfsdfsdfdfsfs schrieb:

dann nach vorne und hinten linear bis zum Ende des Bereichs weiterzusuchen

Such doch binär nach dem Übergang! So eine Suche kann auch mehr als nur ein einzelnes Element angucken.

SeppJ schrieb:

dfsdfsdfdfsfs schrieb:

dann nach vorne und hinten linear bis zum Ende des Bereichs weiterzusuchen

Such doch binär nach dem Übergang!

ok also binär ein element suchen und dann binär nach vorne und hinten den übergang suchen.

werd ich probieren, danke.

falls die elemente der liste wirklich so wiederholend sind, koenntest du eventuel viel zeit sparen wenn du die liste komprimierst indem du jedes element nur einmal speicherst und dazu die anzahl der haeufigkeit.

SeppJ

fsdfsdfsdfsd schrieb:

ok also binär ein element suchen und dann binär nach vorne und hinten den übergang suchen.

Ich würde jetzt spontan sagen: Direkt nach den Übergängen suchen. Wenn du das Suchkriterium

if (dieses element passt && vorheriges element passt nicht)

formulierst (bzw. mit dem Nachfolger), dann wird das zweite Element schließlich gar nicht erst angeguckt, wenn das erste nicht passt (Voraussetzung: C oder andere Sprache mit Kurzschlussauswertung).

Das wäre die Funktion in C++: http://en.cppreference.com/w/cpp/algorithm/equal_range

Eine optimierte Variante könnte so aussehen:
[a,b] ist der mögliche Bereich für die Cs.
Starte mit [0,n], mach binary search bis ein beliebiges C gefunden wurde und verkleinere in jedem Schritt den Bereich entsprechend. Man hat dann [x,y], wobei an x und y kein C gefunden wurde, an (x+y)/2 aber schon.
Dann macht man Binary search in [x, (x+y)/2] für das erste C und in [(x+y)/2,y] für das letzte.

binäre suche in die mitte und danach binäre suche nach beiden seiten um die ränder zu finden geht ruck zuck!
danke nochmal!