BinarySearchArray

See Also: Array Functions, CountArray, SearchArray, Working with Arrays

Purpose

Returns the index of an element in the array (or indicated element range) equal to a particular value. BinarySearchArray is very efficient for large arrays and assumes you are searching for a unique item in a sorted array. If there is or may be more than a single unique matching item, it guarantees finding a match if one exists, but not necessarily the first matching item in the array. To be sure you find the first matching item in an array with more than a single possible matching item, use SearchArray.

Return Type

Integer

Syntax

Simple Search:
(BinarySearchArray( {SearchVal}, {SortedArrayId} [, {bLinguistic} ] )

Extended Search:

    (BinarySearchArray( {SearchVal}, {SortedArrayId} [, {ObjectId} , {MessageId} ])

Where:

What it Does

Iterates from the first to the last element in an array and compares each element to the passed in value {SearchVal} or uses a custom function for the comparison. The index of the first element whose value is equal to {SearchVal} is returned. If no element with a value equal to {SearchVal} is found, -1 is returned.

The array must be sorted (use SortArray) prior to calling BinarySearchArray.

The simple search style lets the runtime do all the work, while the expanded style requires that you create a function to do the comparison.

You can use the simple search style for arrays of any simple data type and arrays of structs where the first struct member is a simple data type.

If the short style of the function is used with an array, a smart comparison will be applied where the first member of the struct will be used for the comparison. Assuming that the first member is a simple data type (String, Integer, etc., not a struct or array), the search will be applied on that member based on the data type of that first member. Not only does this simplify coding, it allows the runtime to perform all comparisons without sending messages, which is much faster.

DataFlex implements different sorting algorithms for different data types in the runtime, in order to provide developers with the most efficient comparison method based on the data type. Algorithms provided in the runtime will also run faster. To use the internal comparison algorithms, simply do not pass the optional ObjectId and MessageId parameters. We recommend the use of these internal algorithms whenever there is no strong reason for a developer to use a special comparison.

To determine the number of times a value occurs in array, use CountArray. For a more efficient search of large arrays, use BinarySearchArray.

If a BinarySearchArray search results in -1 (not found), BinarySearchInsetPos returns the position in an array where a missing item should be inserted.

Binary vs Linguistic

DataFlex supports two styles of sorting strings. The default is linguistic sorting which sorts according to the localization settings (DF_LOCALE_CODE). This results in a sort order that is sensible for humans but the actual sorting itself is a little slower. When passing False as the third (bLinguistic) parameter strings are compared as binary data (per code unit) which is much faster. This results in a sort order that is perfectly sensible for computers but can be illogical for humans (especially regarding extended characters).  Use the binary sort order when sorting arrays to be able to search them quickly.

Special Note: It is important to know that BinarySearchArray and SortArray are both executed in the same mode. So if you call SortArray(…, False) you should also call with BinarySearchArray(.., .., False)!

 

Custom Comparison Function for Extended Search

The developer has the option of providing a custom comparison function for the sorting process if a custom function is desired or required (for arrays of variant and struct arrays where the search cannot use the first struct member or needs to search for multiple struct members).

The function provided in {MessageId} must follow the following syntax:

Function MyCompareFunc {array-element-type} arg1 {array-element-type} arg2 Returns Integer

This function must return one of these values:

You can use a single custom comparison function for a specific data type for all array functions that require one (BinarySearchArray, BinarySearchInsertPos, CountArray, MinArray, MaxArray, SearchArray, SortArray).

 

Simple Array Search

You can use the simple search style to search arrays of simple data types or arrays of structs where the first struct member is a simple type.

Example

String array search:

This sample populates a dynamic array of strings (sCustomers), then searches it for the string "Jones". If the string is found, it displays the element in which the search term was found to the screen, otherwise a message stating that the string was not found is displayed. Last, the values of each array element is displayed to the screen.

This is really not a representative sample, since for an array of only 7 elements, you would use SearchArray rather than BinarySearchArray, but the sample shows you the proper syntax for this function.

// fires when the button is clicked

Procedure OnClick

    String[] sCustomers

    String sSearchTerm

    Integer iSearchIndex

 

    Move "Smith" to sCustomers[0]

    Move "Rodriguez" to sCustomers[1]

    Move "Smith" to sCustomers[2]

    Move "Jones" to sCustomers[3]

    Move "Anderson" to sCustomers[4]

    Move "Schmidt" to sCustomers[5]

    Move "Verne" to sCustomers[6]

    

    // array MUST BE SORTED prior to calling BinarySearchArray

    Move (SortArray(sCustomers)) to sCustomers

 

    // search for "Jones" in array

    Move "Jones" to sSearchTerm

    Move (BinarySearchArray(sSearchTerm, sCustomers)) to iSearchIndex

    If (iSearchIndex <> -1) Begin

        Showln "The search value " sSearchTerm " was found in element " ;

            (String(iSearchIndex))

    End

    Else Begin

        Showln "The search value " sSearchTerm " was NOT found"

    End

End_Procedure

Example

Case-insensitive string array search:

Searching a string array in a case-insensitive manner is a common task, so the runtime provides a predefined function for case-insensitive string comparison: DFSTRICMP, defined in the Desktop object.

Syntax

(BinarySearchArray( {SearchVal}, {ArrayId} , Desktop , (RefFunc(DFSTRICMP)) ))

This sample populates a dynamic array of strings (sCustomers), then searches it for the string "jones", no matter what the casing of any occurrence of "jones", in the sCustomers array. If the string is found, it displays the element in which the search term was found to the screen, otherwise a message stating that the string was not found is displayed. Last, the values of each array element is displayed to the screen.

Between the last insertion into the array and the first call to BinarySearchArray the array must be sorted using SortArray. You must use the same comparison function to sort the array as you use in the call to BinarySearchArray.

This is really not a representative sample, since for an array of only 7 elements, you would use SearchArray rather than BinarySearchArray, but the sample shows you the proper syntax for this function.

// fires when the button is clicked

Procedure OnClick

    String[] sCustomers

    String sSearchTerm

    Integer iSearchIndex

 

    Move "Smith" to sCustomers[0]

    Move "Rodriguez" to sCustomers[1]

    Move "Smith" to sCustomers[2]

    Move "JOnes" to sCustomers[3]

    Move "Anderson" to sCustomers[4]

    Move "Schmidt" to sCustomers[5]

    Move "Verne" to sCustomers[6]

    

    // array MUST BE SORTED using a CASE-INSENSITIVE SORT prior to calling BinarySearchArray

    Move (SortArray(sCustomers, Desktop, (RefFunc(DFSTRICMP)))) to sCustomers

 

    // search for "jones", in any casing, in array

    Move "jones" to sSearchTerm
    Move (BinarySearchArray(sSearchTerm, sCustomers, Desktop, (RefFunc(DFSTRICMP)))) ;

        to iSearchIndex

    If (iSearchIndex <> -1) Begin

        Showln "The search value " sSearchTerm " was found in element " ;

            (String(iSearchIndex))

    End

    Else Begin

        Showln "The search value " sSearchTerm " was NOT found"

    End

End_Procedure

 

Simple Struct Array Search:

You can use the simple search style for arrays of any simple data type and arrays of structs where the first struct member is a simple data type.

If the short style of the function is used with an array, a smart comparison will be applied where the first member of the struct will be used for the comparison. Assuming that the first member is a simple data type (String, Integer, etc., not a struct or array), the search will be applied on that member based on the data type of that first member. Not only does this simplify coding, it allows the runtime to perform all comparisons without sending messages, which is much faster.

One way to take advantage of this is to design structs that use a unique identifier as the first member, allowing a runtime search of an array of such structs to find any struct and then access the rest of the information in that struct.

Example

This sample shows how to find a friend with id 5 in an array filled with 10 tFriend structs.

In Procedure OnClick, MyFriends is declared as a tFriend array and populated with 10 friends' Ids and names. Another struct of type tFriend is declared to store the search value. Since the search is for a struct in an array of that struct where the first member of the struct is a simple type, a custom search function is not required.

The SearchFriend struct is filled with the value being searched for; since the search only compares the first member (iFriendId) of each struct in the array, there is no need to place values in the other members of this struct.

Struct tFriend

    Integer iFriendId

    String First

    String Last

End_Struct

 

Procedure OnClick

    // declare array of 10 tFriend structs

    tFriend[10] MyFriends

 

    // declare tFriend struct that will hold search value(s)

    tFriend SearchFriend

 

    Integer iSearchIndex

 

    // fill MyFriends array

    Move 1           to MyFriends[0].iFriendId

    Move "Janet"     to MyFriends[0].First

    Move "Smith"     to MyFriends[0].Last

    Move 2           to MyFriends[1].iFriendId

    Move "Pedro"     to MyFriends[1].First

    Move "Rodriguez" to MyFriends[1].Last

    Move 3           to MyFriends[2].iFriendId

    Move "Judy"      to MyFriends[2].First

    Move "Smith"     to MyFriends[2].Last

    Move 4           to MyFriends[3].iFriendId

    Move "Fred"      to MyFriends[3].First

    Move "Jones"     to MyFriends[3].Last

    Move 5           to MyFriends[4].iFriendId

    Move "Martin"    to MyFriends[4].First

    Move "Anderson"  to MyFriends[4].Last

    Move 6           to MyFriends[5].iFriendId

    Move "Michael"   to MyFriends[5].First

    Move "Schmidt"   to MyFriends[5].Last

    Move 7           to MyFriends[6].iFriendId

    Move "Jacques"   to MyFriends[6].First

    Move "Verne"     to MyFriends[6].Last

    Move 8           to MyFriends[7].iFriendId

    Move "Enrico"    to MyFriends[7].First

    Move "Ricci"     to MyFriends[7].Last

    Move 9           to MyFriends[8].iFriendId

    Move "Karl"      to MyFriends[8].First

    Move "Sorensen"  to MyFriends[8].Last

    Move 10          to MyFriends[9].iFriendId

    Move "Juan"      to MyFriends[9].First

    Move "Garcia"    to MyFriends[9].Last

 

    // Move value to compare array values to the Comparison struct

    Move 5 to SearchFriend.iFriendId

 

    // array MUST BE SORTED prior to calling BinarySearchArray

    Move (SortArray(MyFriends)) to MyFriends

 

    Move (BinarySearchArray(SearchFriend, MyFriends)) to iSearchIndex

    If (iSearchIndex <> -1) Begin

        Showln "The search value was found in struct number " (String(iSearchIndex))

    

        // display the values in the found struct

        Showln ":" MyFriends[iSearchIndex].iFriendId ":" MyFriends[iSearchIndex].First ;

            ":" MyFriends[iSearchIndex].Last ":"

    End

End_Procedure

 

Example

Extended struct array search:

This sample shows how to find a friend with last name "Jones" are in an array of 10 tFriend structs. A custom comparison function is used to determine how array elements are compared.

In Procedure OnClick, MyFriends is declared as an array of 10 elements of type tFriend and populated with friends' names. Another struct of type tFriend is declared to store the search value. Since our comparison function only compares the Last member (last name) of each struct in the array, the First struct member is not filled with any value.

Struct tFriend

    String First

    String Last

End_Struct

 

// Custom comparison function:

//   Returns (GT) struct value in first parameter > struct value in second parameter.

//   Returns (LT) struct value in first parameter < struct value in second parameter.

//   Otherwise returns (EQ).

Function CompareFriends tFriend Friend1 tFriend Friend2 Returns Integer

    If (Friend1.Last > Friend2.Last) ;

        Function_Return (GT)

    If (Friend1.Last < Friend2.Last) ;

        Function_Return (LT)

 

    Function_Return (EQ)

End_Function

 

// fires when the button is clicked

Procedure OnClick

    // declare array of tFriend structs

    tFriend[] MyFriends

    // declare tFriend struct that will hold search value(s)

    tFriend SearchFriend

    Integer iSearchIndex

 

    // move value to compare array values to the Comparison struct

    Move "Jones" to SearchFriend.Last

 

    // add 10 friends to MyFriends array

    Move "Janet" to MyFriends[0].First

    Move "Smith" to MyFriends[0].Last

    Move "Pedro" to MyFriends[1].First

    Move "Rodriguez" to MyFriends[1].Last

    Move "Judy" to MyFriends[2].First

    Move "Smith" to MyFriends[2].Last

    Move "Fred" to MyFriends[3].First

    Move "Jones" to MyFriends[3].Last

    Move "Martin" to MyFriends[4].First

    Move "Anderson" to MyFriends[4].Last

    Move "Michael" to MyFriends[5].First

    Move "Schmidt" to MyFriends[5].Last

    Move "Jacques" to MyFriends[6].First

    Move "Verne" to MyFriends[6].Last

    Move "Enrico" to MyFriends[7].First

    Move "Ricci" to MyFriends[7].Last

    Move "Karl" to MyFriends[8].First

    Move "Sorensen" to MyFriends[8].Last

    Move "Juan" to MyFriends[9].First

    Move "Garcia" to MyFriends[9].Last

 

    // array MUST BE SORTED prior to calling BinarySearchArray

    // call CompareFriends function to sort array elements

    Move (SortArray(MyFriends, Self, get_CompareFriends)) to MyFriends

 

    // call CompareFriends function to search array elements for value(s) in SearchFriend

    Move (BinarySearchArray(SearchFriend, MyFriends, Self, get_CompareFriends)) ;

        to iSearchIndex

 

    If (iSearchIndex <> -1) Begin

        Showln "The search value was found in element number " (String(iSearchIndex))

    End

End_Procedure

Example

Searching a single dimension of a multi-dimensional array:

This sample declares a 2 dimensional string array with 8 (2x4) elements and fills it with unsorted string values. This creates an array as such:

    Smith Rodriguez Scott Jones

    Anderson Schmidt Verne Ricci

If the first "row" (row 0) of the array is searched, the search term "Jones" is found in element 3. If the second "row" (row 1) of the array is searched, the search term "Jones" is not found. This effectively limits the search to a specific "row" of the array.

Procedure OnClick

    String[][] sCustomers

    String sSearchTerm

    Integer iSearchIndex

 

    Move "Smith"     to sCustomers[0][0]

    Move "Rodriguez" to sCustomers[0][1]

    Move "Scott"     to sCustomers[0][2]

    Move "Jones"     to sCustomers[0][3]

    Move "Anderson"  to sCustomers[1][0]

    Move "Schmidt"   to sCustomers[1][1]

    Move "Verne"     to sCustomers[1][2]

    Move "Ricci"     to sCustomers[1][3]

 

    // search for "Jones" in first "row" of array

    Move "Jones" to sSearchTerm

    Move (SortArray(sCustomers[0])) to sCustomers[0]

    Move (BinarySearchArray(sSearchTerm, sCustomers[0])) to iSearchIndex

    If (iSearchIndex <> -1) Begin

        showln "The search value " sSearchTerm " was found in element " ;

            (String(iSearchIndex))

    End

    Else Begin

        showln "The search value " sSearchTerm " was NOT found"

    End

 

    // search for "Jones" in second "row" of array

    Move "Jones" to sSearchTerm

    Move (SortArray(sCustomers[1])) to sCustomers[1]

    Move (BinarySearchArray(sSearchTerm, sCustomers[1])) to iSearchIndex

    If (iSearchIndex <> -1) Begin

        showln "The search value " sSearchTerm " was found in element " ;

            (String(iSearchIndex))

    End

    Else Begin

        showln "The search value " sSearchTerm " was NOT found"

    End

End_Procedure

Sorting and Searching via RowId

You can search and sort on RowId. This affects SearchArray(), BinarySearchArray(), CountArray()and SortArray(). The sort order of RowIds has no real meaning and its actual sort order is undefined. The reason for sorting RowIds is it can allow faster searching when used with BinarySearchArray().