Binary Search


Once you sort a list of items, you can search it quickly with a binary search. A binary search splits the list into two parts, determines which one contains the search item, and then searches only that part by splitting that list into two parts. It continues in this fashion until the item is found. You can also use a binary search to insert an item into a sorted list. Instead of inserting the item at the beginning or at the end and then re-sorting, you search the list for the appropriate place to insert the item.


The BSearchArray function uses the same helper object as SortArray and Shuffle­Array. It uses the Compare method but doesn’t need the Swap method.

Function BSearchArray(av() As Variant, ByVal vKey As Variant, _
                      iPos As Long, _
                      Optional helper As ISortHelper) As Boolean
    Dim iLo As Long, iHi As Long
    Dim iComp As Long, iMid As Long
    If helper Is Nothing Then Set helper = New CSortHelper
    
    iLo = LBound(av): iHi = UBound(av)
    Do
        iMid = iLo + ((iHi - iLo) \ 2)
        iComp = helper.Compare(av(iMid), vKey)
        Select Case iComp
        Case 0
            ‘ Item found
            iPos = iMid
            BSearchArray = True
            Exit Function
        Case Is > 0
            ‘ Item is in lower half
            iHi = iMid - 1
            If iLo = iHi Then Exit Do
        Case Is < 0
            ‘ Item is in upper half
            iLo = iMid + 1
            If iLo > iHi Then Exit Do
        End Select
    Loop
    ‘ Item not found, but return position to insert
    iPos = iMid - (iComp < 0)
        
End Function

For an interesting example of binary search, check out the sorted list box control discussed in Chapter 11. This control uses a binary search procedure to
insert new list items at the correct location in a sorted list box.


In addition to procedures for sorting, shuffling, and searching arrays, SORT.BAS contains similar procedures for collections. Sorting arrays and sorting collections are different enough to require separate procedures but not different enough to justify separate discussions. Both versions depend on the Compare method, but swapping works differently in collections. I’ll let you figure out the details from the source.