Find in sorted array

Home

4D v16.3


Find in sorted array ( Array ; Wert ; > oder < {; ErstePos {; LetztePos}} ) -> Funktionsergebnis

Parameter	Typ	Beschreibung
Array	Array	Array zum Suchen
Wert	Ausdruck	Wert (gleicher Typ wie Array) zum Suchen im Array
> oder <	Operator	> wenn Array in aufsteigender Reihenfolge sortiert ist, < wenn Array in absteigender Reihefolge sortiert ist
ErstePos	Lange Ganzzahl	Position des ersten Vorkommens, wenn der Wert gefunden wird; sonst Position, an der der Wert eingefügt werden soll.
LetztePos	Lange Ganzzahl	Postion des letzten Vorkommens, wenn der Wert gefunden wird; sonst gleicher Wert wie ErstePos
Funktionsergebnis	Boolean	Wahr, wenn mindestens ein Element im Array zum Wert passt, sonst Falsch

Beschreibung

Die Funktion Find in sorted array gibt wahr zurück, wenn mindestens ein Element im sortierten Array zum Parameter Wert passt. Sie gibt optional auch die Position des Elements zurück. Im Gegensatz zu Find in array funktioniert Find in sorted array nur mit einem sortierten Array und gibt außerdem die Position der Vorkommen an. So lassen sich auch Elemente einfügen, wenn keine Vorkommen gefunden werden.

Das Array muss bereits sortiert und in derselben Reihenfolge sein, wie im Parameter > oder < angegeben wurde, d.h. "größer als" für aufsteigende und "kleiner als" für absteigende Reihenfolge. Andernfalls ist das Suchergebnis u.U. nicht korrekt. Find in sorted array nutzt die Sortierung und einen binären Suchalgorithmus, was bei umfangreichen vorsortierten Arrays in der Regel effektiver ist. Weitere Informationen dazu finden Sie unter Wikipedia, binäre Suche.

In folgenden Fällen ignoriert die Funktion die Sortierrichtung und arbeitet wie die Funktion Find in array (sequentielle Suche, gibt für ErstePos und LetztePos -1 zurück, wenn Wert nicht gefunden wird):

bei Arraytypen, die sich nicht sortieren lassen, wie z.B. Zeiger Arrays,
bei Anwendungen im Nicht-Unicode Modus (Kompatibilitätsmodus) und wenn das Array vom Typ String oder Text ist,
wenn in einem Array vom Typ Text nach einem String mit Joker ('@') am Anfang oder in der Mitte gesucht wird. Hier ist kein binärer Suchalgorithmus möglich, da die passenden Elemente im Array evtl. nicht in fortlaufender Reihenfolge sind.

Gibt die Funktion False zurück, kann der in ErstePos zurückgegebene Wert an INSERT IN ARRAY übergeben werden, um den Wert in das bereits vorsortierte Array einzufügen. Das läuft schneller, als erst einen neuen Eintrag ans Ende des Array zu setzen und dann SORT ARRAY aufzurufen, um es an die richtige Stelle zu bewegen.

Die in LetztePos und ErstePos zurückgegebenen Werte lassen sich miteinander kombinieren, um jedes Element des Arrays zu durchlaufen, das zu Wert passt (mit einer For...End for Schleife) oder um die Anzahl der Vorkommen zu finden (wie auch mit dem Befehl Count in array, nur schneller).

Beispiel 1

Bei Bedarf einen Wert einfügen und dabei das sortierte Array beibehalten:

 C_LONGINT($pos)

 If(Find in sorted array($array ;$value ;>;$pos)

    ALERT("Found at pos "+String($pos))

 Else

    INSERT IN ARRAY($array ;$pos)

    $array{$pos}:=$value

 End if

Beispiel 2

Die Anzahl der Vorkommen von Strings finden, die mit "test" beginnen und einen String erstellen, der diese Elemente zusammenfasst:

 C_LONGINT($posFirst ;$posLast)

 C_TEXT($output)

 If(Find in sorted array($array ;"test@";>;$posFirst ;$posLast))

    $output:="Found "+String($posLast-$posFirst+1)+" results :\n"

 End if

 For($i ;$posFirst ;$posLast)

    $output:=$output+$array{$i}+"\n"

 End for

Siehe auch

Count in array
Find in array
SORT ARRAY