Find in sorted array

Home

4D v20 R7


Find in sorted array ( array ; value ; > or < {; posFirst {; posLast}} ) -> Function result

Parameter	Type	Description
array	Array	Array to search
value	Expression	Value (same type as array) to search for in the array
> or <	Operator	> if array is sorted in ascending order, < if it is sorted in descending order
posFirst	Longint	Position of its first occurrence if the value is found; otherwise position where the value should be inserted
posLast	Longint	Position of its last occurrence if the value is found; otherwise same as posFirst
Function result	Boolean	True if at least one element in array matches the value, False otherwise

Description

The Find in sorted array command returns true if at least one element in the sorted array matches the value, and optionally returns position(s) of matched element(s). Unlike Find in array, Find in sorted array only works with a sorted array and provides information about the position of occurrences, which allows you to insert elements if necessary.

The array must be already sorted and must match the ordering specified by the > or < parameter (i.e. the "greater than" symbol for ascending order and the "lower than" symbol for descending order). The Find in sorted array command will take advantage of the sort and use a binary search algorithm, which is much more efficient for large arrays (for more information, please refer to the binary search algorithm page on Wikipedia). However, if the array is not properly sorted, the result may be incorrect.

Note: When using this command with a sorted array of type Object, you can only pass an object reference in value.

The command will ignore the sort indication and behave like a standard Find in array (sequential search, returning -1 for posFirst and posLast if the value is not found) in any of the following cases:

if the array type cannot be sorted (e.g. pointer arrays),
if the array is of type boolean (not accurate),
if the database is not Unicode (compatibility mode) and the array is a string or text array,
when searching in a text array for a string that includes a wildcard ('@') at the beginning or in the middle of the string (using a binary search with such a wildcard character is not possible because matching elements may be non-contiguous in the array).

In case the command returns False, the value returned in posFirst can be passed to INSERT IN ARRAY to insert the value into the array while keeping the array sorted. This sequence is faster than inserting a new item at the end of the array and then calling SORT ARRAY to move it to the right place.

The value returned in posLast can be combined with the value returned in posFirst to iterate on each element of the array matching the value (with a ARRAY TO LIST loop) or to find the number of occurrences (as would be found by Count in array, but faster).

Example 1

You want to insert a value, if necessary, while keeping the array sorted:

 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

Example 2

You want to find the number of occurrences of strings starting with "test" and create a string that concatenates all these elements:

 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