# String-Interpolationssuche?



## bröggle (14. Apr 2005)

Hi,
*hust* (ich muss erstmal den staub von meinem account entfernen)

und zwar habe ich das problem, dass ich einen algo für die interpolierte Suche erstellen soll.
Soweit kein problem (im inet gibt es ja genügend Beispiele für die interpolierte Suche für Zahlen), aber ich 'muss'/möchte nach einem String suchen.

d.h. einen String aus einem Stringarray raussuchen.

->Problem dabei die neuen teilbereiche zu berechnen.

so wie hier: http://de.wikipedia.org/wiki/Interpolationssuche geht es eben nicht (ich kann ja nicht mit 'foo' malnehmen)


Meine Fragen also:
Geht eine Interpolierte Suche überhaupt mit Strings (muss eigentlich)
2.Wenn ja wie, bzw hat jemand ein Beispiel?bzw kann mir jemand erklären wie ich die neuen teilbereiche rausbekomme?
Denn sowas wie indexOf werde ich ja wohl nicht nehmen dürfen


Danke schonmal
^-^


----------



## stev.glasow (14. Apr 2005)

Und wenn du den hashcode des Strings nimmst?


----------



## bröggle (14. Apr 2005)

stevg hat gesagt.:
			
		

> Und wenn du den hashcode des Strings nimmst?


hmm, habe ich mir auchs chon überlegt,
aber ist der hashcode von abc auch wirklich kleiner als der von zz?


----------



## stev.glasow (14. Apr 2005)

Ne größer weil abc mehr Zeichen hat. Auf'n Schlag wüsste ich aber auch nix anderes  ???:L


----------



## bröggle (14. Apr 2005)

hmm, könnte man dann nicht 
den sting mit vielen Z (letztes in sortierung) füllen, sodass zumindest die Stellen zahl gleich wäre?

ZZZZabc <
ZZZZZzz

würde ja wieder stimmen.
aber welche hashfunktion kann das so machen?
bzw welche liefert eine entsprechende Zahl zurück


----------



## stev.glasow (14. Apr 2005)

hab doch was zusammen gefriemelt bekommen, hab den Code von Wikipedia etwas angepasst:

```
public static int interpolierteSuche(String schlüssel, String daten[])
	 {
	   int links = 0;                  // linke Teilfeldbegrenzung 
	   int rechts = daten.length - 1;  // rechte Teilfeldbegrenzung
	   int versch;                     // Anzahl verschiedener Elemente
	   int pos;                        // aktuelle Teilungsposition

	   // solange der Schlüssel im Bereich liegt (andernfalls ist das gesuchte 
	   // Element nicht vorhanden)
	   while( schlüssel.compareTo(daten[links]) >= 0 && schlüssel.compareTo(daten[rechts]) <= 0 ){
	     // Aktualisierung der Anzahl der verschiedenen Elemente
	     versch = daten[rechts].compareTo(daten[links]);
	        
	     // Berechnung der neuen interpolierten Teilungsposition 
	     pos = links + (int)(((double)rechts - links) * (schlüssel.compareTo(daten[links]))
	           / versch);
	     
	     if( schlüssel.compareTo(daten[pos]) > 0)             // rechtes Teilintervall 
	       links = pos + 1;                       // daten[pos] bereits überprüft
	     else if( schlüssel.compareTo(daten[pos])  < 0 )       // linkes Teilintervall
	       rechts = pos - 1;                      // daten[pos] bereits überprüft
	     else                                     // Element gefunden
	       return pos;                            // Position zurückgeben
	   }
	        
	   return -1;                                 // Element nicht gefunden
	 }
```


----------



## stev.glasow (14. Apr 2005)

Scheiße geht doch nicht, nur wenn die Strings nur aus Zahlen bestehen, was dir ja gar nix bringt.
[edit] Und dann auch nicht richtig, den Code kannst du in die Tonne kloppen.


----------



## bröggle (14. Apr 2005)

hehe, trotzdem danke für deine mühe;-)

Die Hashcode-Methode ist ansich eine ganz gute Ideejeoch funktioniert das nur bis zu einer bestimmten stringlänge... z.b. bei 10Stellen gibt es - Zahlen und das ganze hat sich erledigt:

CCCCCCCCCD	997603809

DDDDDDDDDE	1653533313	

EEEEEEEEEF	-1985504479	

FFFFFFFFFG	-1329574975	

GGGGGGGGGH	-673645471


----------



## stev.glasow (14. Apr 2005)

Du mein Code oben geht doch, hatte im Test einen Fehler, hatte einen Array übergeben der nicht sortiert war.


----------



## bröggle (14. Apr 2005)

stevg hat gesagt.:
			
		

> Du mein Code oben geht doch, hatte im Test einen Fehler, hatte einen Array übergeben der nicht sortiert war.



Aber nur für Zahlenstrings oder?


----------



## stev.glasow (14. Apr 2005)

ne für alle


----------



## stev.glasow (14. Apr 2005)

ich hab einfach die a - b durch a.compareTo(b) ersetzt und die a >= b durch a.compareTo(b) >= 0 usw. 
Klar was das soll?


----------



## bröggle (14. Apr 2005)

hmm, müsste ich ja fast mal ausprobieren ;-)

tja ansich einfach ;-)(hoffe ich)


----------



## bröggle (14. Apr 2005)

juhuhuhuhu geht!


;-)
eigentlich wars ganz logisch, aber da fehlts mir noch ein wenig an erfahrung ;-)

Naja vielleicht wirds ja dann im Studium besser


Danke


p.s.: wünscht mir glück für den 28.4, 2.5 und 12.5 (ABI)


----------



## stev.glasow (14. Apr 2005)

> p.s.: wünscht mir glück für den 28.4, 2.5 und 12.5 (ABI)


 nö


----------



## ohNein (20. Aug 2008)

stevg hat gesagt.:
			
		

> hab doch was zusammen gefriemelt bekommen, hab den Code von Wikipedia etwas angepasst:
> 
> ```
> public static int interpolierteSuche(String schlüssel, String daten[])
> ...



Nur das die ganze Sache nicht das hält was es verspricht.
Es soll ja eine günstige position für das suchen gefunden werden.
CompareTo liefert aber nur -1,0,1 und bringt somit nicht viel bei der Berechnung der Position


----------



## GilbertGrape (21. Aug 2008)

Das is doch schon 3 Jahre alt...


----------

