Binäre suche eines strings in einer tabelle

Wenn du nicht mindestens 50 Einträge in deiner Liste hast dann vergiss
das mit der binären Suche ganz schnell. Der Codieraufwand ist viel zu
gross.

Durchlauf einfach deine Liste bis du den richtigen Eintrag gefunden
hast. Wenn du darauf achtest dass die Strings sortiert in der Liste
abgelegt sind kannst du die Suche abbrechen wenn der String in der
Liste alphabetisch grösser ist als der gesuchte Stringwert.

P.S Die von dir dargestellte Struktur wird wohl kein Compiler so
übersetzen können :-(

ich hab aber weit über 50 einträge...dass nur 3 Parameter in der List
sind, ist nur ein Beispiel....

Dann überleg mal die Logik der binären Suche, dann kannst du dir deine
Suchfunktion ganz einfach selber schreiben.

Angenommen du hast 80 Einträge in der List, welche sortiert(!)
vorliegt.
Jetzt vergleichst du den mittleren (40sten) Eintrag der Liste mit dem
zu suchenden Schlüsselwort.
Ist der Eintrag in der Liste kleiner als das gesuchte Wort dann suchst
du in der unteren Hälfte der Liste weiter.
Ist der Eintrag in der Liste grösser als das gesuchte Wort dann suchst
du in der oberen Hälfte weiter.
Dazu verwendest du am besten 2 Schleppvariablen (z.B. nLow, nHigh)
welche du zu Beginn der Suche mit dem minimalen (0) und maximalen (in
unserem Beispiel 79) Arrayindex initialisierst.
Wenn bei der Suche nHigh plötzlich kleiner als nLow wird dann konnte
der Eintrag nicht gefunden werden.

danke...
und was passiert, wenn die strings unterschiedliche Länge habe?....zum
vergleich verwende ich die fertige funktion "strcmp" von c

Hallo sam,

IMHO würde ich nicht mit strcmp vergleichen, sondern immer nur das
nächste Zeichen, das noch nicht passte.

Bsp:
Eingabe = Hallo ; Liste = {Alpha, Hallo, Lima, Tango, Yankee}

Nun legst Du los mit:
unsigned char macht_position(void) {
 nhigh = 4, nlow = 0;
 npos = (nhigh - nlow) / 2
 matchpos = 0;
 matchmax = 3;
 if (Liste [npos][matchpos] > Eingabe[matchpos) nhigh = npos;
 if (Liste [npos][matchpos] < Eingabe[matchpos) nhigh = npos;
 if (Liste [npos][matchpos] == Eingabe[matchpos) {
    if (matchpos < matchmax)  matchpos ++;
    else
     if (strcmp (Liste[npos], Eingabe, strlen(Eingabe)) ) return TRUE;
     else return FALSE;
 }
}
Was passiert ist folgendes:
Ist Eingabe an der ersten Stelle kleiner als die erste Stelle der
Eingabe, dann wird im oberen Teil der Liste weiter nachgeschaut. Man
halbiert also immer die betrachtete Menge.
Weiterhin weiß ich, bis zu welcher Steelle maximal Unterschiede
auftauchen können - matchmax.
Nun benutze ich den oberen Algorithmus so lange, bis dies ich diese
Tiefe erreichen und weiß, das mein betrachteter String bis dort
übereinstimmt. Schlußendlich schaue ich noch mit strcmp nach obs
wirklich so ist und geb dann den entsprechenden Wert zurück.
Dies ist wesendlich schneller, als die strcmp Funktion, die jedesmal
den gesamten STring vergleicht.

Gruß Marcus

Hallo,

das Zauberwort lautet bsearch und qsort!

bsearch tut genau das, was  Christian erläutert. Ist dein Array von
Strings noch nicht sortiert, verwendest du dazu die Funktion qsort.

Sowohl bei bsearch als auch bei qsort gibst du eine Vergleichsfunktion,
die du nach belieben ausprogrammieren kannst.

Beide Funktionen sollten auch auf uC problemlos funktionieren.
'qsort' kannst du natürlich nicht auf Strings im Flash anwenden, die
müssen vorher schon sortiert sein.



Gruss,

Peter