Skip to content

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 ensure that the array is 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