Flamefire - Di 25.08.09 22:10
Titel: IntegerArray schnell durchsuchen

---

Hi,
ich bräuchte mal ein stück code, mitdem ich ein einfaches (1D), dynamisches Integer array nach einem wert durchsuchen kann
die werte werden nach und nach eingefügt.
es soll aber häufiger (wärend des einfügens) geprüft werden, ob ein bestimmter wert schon existiert.
eine lineare suche ist mir zu langsam...

ich kenne die möglichkeiten die es gibt (binärbaum aufstellen, AVL-Baum usw...) hätte diesmal aber gern einfach nen stück code, dass ich einfügen kann, falls das jmd rum liegen hat, oder weiß wo es steht ;-)

Xentar - Di 25.08.09 22:20

---

Über wie viele Einträge reden wir hier?
Und, sind diese irgendwie sortiert, oder liegen die Werte wild durcheinander?

Flamefire - Di 25.08.09 22:27

---

es sind zwischen maximal 4000 und 35000 werte (je nach aktueller aufgabe)
(maximal, da ja die werte nach und nach geschrieben werden)

die werte sind überwiegend aufsteigend sortiert, aber nicht vollständig

Tastaro - Mi 26.08.09 11:05

---

Flamefire hat folgendes geschrieben :

die werte sind überwiegend aufsteigend sortiert, aber nicht vollständig

Dann hilft nur eine sequentielle Suche, wie du es jetzt schon machst oder du baust dir in irgendeiner Form einen Index auf.
Für den Index kann man die von dir genannten Bäume oder eine sortierte Indexliste nehmen in der man dann mit einer Binärsuche suchen kann.

Code daszu findest du ziemlich sicher hier im Forum mit Hilfe der Suchfunktion oder auch bei Wikipedia.

Beste Grüße