BinarySearchInsertPos

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

Purpose

Returns the position in an array where a missing item should be inserted.

Return Type

Integer

Syntax

(BinarySearchInsertPos() )

What it Does

Returns the position in an array where a missing item should be inserted. It must be called immediately following a BinarySearchArray call that returned no result.

If a binary search applied to a sorted array fails to find the target, it returns -1.

Move (BinarySearchArray(Target, MySortedArray)) to iIndex // if -1, not found  

Move (BinarySearchArray(Target, MySortedArray,hoObject,hMsg)) to iIndex // if -1, not found  

This only tells you that the item was not found. If you immediately call BinarySearchInsertPos following that failed search, it will return the position in the array where the missing item should have been found, which is the position where it should be inserted.

You can use this value with the InsertInArray to add the missing item to the array. This provides a mechanism for adding items to an already sorted array without needing to resort the entire array.

Move (BinarySearchArray(Target, MySortedArray)) to iIndex // if -1, not found  

If (iIndex = -1) Begin

    Move (BinarySearchInsertPos()) to iIndex

    Move (InsertInArray(MySortedArray, iIndex,Target)) to MySortedArray

End

As with any binary search operation, it is the developer's responsibility to make sure that the array was properly sorted. The developer must also make sure that BinarySearchInsertPos is called before any other array search is performed.

Inserting an item into a very long array has a performance penalty as the array has to be shifted to make room for a new item. Appending values to an array is always the fastest way to add an item. Sorting an array also has an overhead but often this occurs only once after all items are added. With very large arrays, inserting a limited number of items into their sorted position may be faster than appending the items and then sorting them.

Example

This example shows how to check a string array for the presence of a specific item (Customer name in this case), determine where in the array it belongs if it's not there already, and insert it.

Procedure OnClick

    String[] sCustomers

    String sSearchTerm

    Integer iSearchIndex i iArraySize

    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 "Nimoy", in any casing, in array

    Move "Nimoy" to sSearchTerm

    // perform a case-insensitive search for the search term

    Move (BinarySearchArray(sSearchTerm, sCustomers, Desktop, (RefFunc(DFSTRICMP)))) to iSearchIndex

    If (iSearchIndex = -1) Begin  // item is not already in the array

        Move (BinarySearchInsertPos()) to iSearchIndex

        If (iSearchIndex <> -1) Begin  // the position to insert the new item was found

            Move (InsertInArray(sCustomers, iSearchIndex, sSearchTerm)) to sCustomers

        End

    End

    // display array values

    Move (SizeOfArray(sCustomers)) to iArraySize

    For i from 0 to (iArraySize-1)

        Showln sCustomers[i]

    Loop

End_Procedure