BinarySearchArray

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 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 one possible matching item, use SearchArray.

Return Type

Integer

Syntax

Simple search:

BinarySearchArray( {SearchVal}, {SortedArrayId} [, {bLinguistic} ] )

Extended search:

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

Parameters

{SearchVal}
The value to compare array elements' values to. The index of the first element whose value is equal to {SearchVal} is returned.
{SortedArrayId}
The id of the array being searched. Array must be sorted, non-jagged and one dimensional (it can be a single dimension of a multi-dimensional array).
{ObjectId}
The id of the object that implements the comparison function (for the extended form).
{MessageId}
The id of the function that will be used to compare two array elements (for the extended form).
{bLinguistic} (optional)
If True, a linguistic comparison is done according to the localization rules configured by DF_LOCALE_CODE. Read more in the Binary vs Linguistic section below.

What it Does

BinarySearchArray performs a binary search on a sorted one-dimensional array (or one dimension of a multi-dimensional array) and returns the index of an element equal to the given search value. If no matching element is found, -1 is returned.

The array must be sorted (use SortArray) prior to calling BinarySearchArray.
The simple search format lets the runtime do the comparison work internally.
The extended format requires you to provide a custom comparison function (ObjectId and MessageId).

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

If the short/simple style is used with an array of structs, the runtime performs a smart comparison using the first member of the struct. The first member must be a simple data type (String, Integer, etc.). This avoids message passing and is much faster than a custom comparison.

DataFlex implements optimized internal comparison algorithms for different data types. To use these internal algorithms, omit the optional ObjectId and MessageId parameters. Use the internal algorithms unless you have a specific reason to supply a custom comparison.

To determine the number of times a value occurs in an array, use CountArray. If BinarySearchArray returns -1 (not found), BinarySearchInsertPos returns the position in the array where a missing item should be inserted.

Binary vs Linguistic

DataFlex supports two styles of sorting strings:

Linguistic (default): sorts according to localization settings (DF_LOCALE_CODE). This is sensible for humans but slightly slower.
Binary: compares strings as binary data (per code unit), which is faster but may produce an order that is less intuitive for humans (especially for extended characters).

Use binary sort order when sorting arrays to be searched quickly. Note: BinarySearchArray and SortArray must be executed in the same mode. If you call SortArray(..., False) you should also call BinarySearchArray(..., ..., False).

Custom Comparison Function for Extended Search

You can provide a custom comparison function to control how elements are compared (required for arrays of variant and for struct arrays where the first struct member is not usable for comparison or when comparing multiple members).

The function provided in {MessageId} must follow this syntax:

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

The function must return one of these values:

GT — if the first parameter is greater than the second parameter
EQ — if the parameters are considered equal
LT — if the first parameter is less than the second parameter

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

Simple Array Search

The simple search style works for arrays of simple data types and for arrays of structs where the first struct member is a simple type. The runtime will compare using that first member automatically.

Examples

Example 1 — String array search

Populates a dynamic array of strings (sCustomers), sorts it, then searches it for "Jones". If found, the element index is displayed; otherwise a not-found message is displayed.

// 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 2 — Case-insensitive string array search

The runtime provides a predefined case-insensitive comparison function: DFSTRICMP (defined in the Desktop object). Use the same comparator for both SortArray and BinarySearchArray.

// 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

Example 3 — Simple struct array search

If the first struct member is a simple type, the simple search style can be used and no custom comparator is required. This example finds a friend with id 5 in an array of 10 tFriend structs.

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 4 — Extended struct array search

This example searches an array of tFriend structs by last name using a custom comparison function CompareFriends.

Struct tFriend
    String First
    String Last
End_Struct

// Custom comparison function:
//   Returns GT if value in first parameter > value in second parameter.
//   Returns LT if value in first parameter < 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 5 — Searching a single dimension of a multi-dimensional array

This sample declares a 2-dimensional string array (2x4), fills it with unsorted values, then sorts and searches a specific row (dimension).

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 defined meaning; sorting RowIds is useful mainly to allow faster searching when used with BinarySearchArray().