When I had written my sorting component, I soon realized that with the components I had written, I would also be able to perform a search. Now there is lot of stuff written on searching, most of which doesn’t concern us here. Here we are concerned with searching strategies that search SortableContainers (see Sorting).
In this there are really two main options : if the container is sorted you perform a Binary Search an if the container is not sorted you perform a linear search. So what’s the big deal about this article then ?
By using the technology we built when solving our sorting problem, we can create a reusable form of both algorithms that is much like a classic C bsearch or lsearch. To start immediately, here is the implementation of my linear search : ' LinearSearch :
' --------------
' Perform a linear search for the item in the container.
' Item are compared with comparers.
' If found the 1 based index is returned, else -1
' NOTE : if keys appear multiple times it IS necessarily
' the first occurence that will be returned
' NOTE 2 : If you need to search in a certain range, take a look at the cSortableSubRange
' meta container adapter. It keeps our search simpler
Public Function LinearSearch(ByVal objContainer As iSortableContainer, ByVal varItem As Variant, ByVal objCriterium As iComparer) As Long
Debug.Assert Not
(objContainer Is Nothing)
Debug.Assert Not (objCriterium Is Nothing)
Dim nCount As Long
Dim nCurrent As Long
LinearSearch = -1 ' default is not found
With objContainer
nCount = .Count
For nCurrent = 1 To nCount
If objCriterium.Compare(varItem, .Item(nCurrent)) = 0 Then
LinearSearch = nCurrent
Exit For
End If
Next
End With
End Function There is nothing especially earth-shocking in this code.
It searches from the front of the container until it finds a matching item. Please note that in fact the ISortableContainer interface is ‘too heavy’ for searching. While searching, we never use the Swap method. Unfortunately, about the only thing I can do about that is define an interface ISearchableContainer that looks like this : Property Get Item(ByVal nPos
As Long) As Variant
Property Get Count() As Long Unfortunately, this would have forced me to either let all existing containers also implement this smaller interface or create new versions of each with a very high similarity.
Until I do something in .NET (where I could let ISortableContainer extend ISearchContainer), my searching function uses the existing implementations. The same holds for the IComparer interface. While in sorting this interface is symmetric, in searching it is actually assymmetric. It should be something like Function Compare(ByVal SearchValue As Variant, ByVal containerValue As Variant) As Long When searching, the type of the value you search for can be actually quite different from the type of the value you match it against. You can use a
string to search a collection of objects. I stuck with the Icomparer interface for the same reasons I kept ISortableContainer. For ‘Matchers’, we always pass the value being searched as the frist argument while the second argument is a value that comes from the container. With all this being said, it is about time to move to the BinarySearch :
' BinarySearch :
' --------------
' Perform a binary search for the item in the container.
' Item are compared with comparers.
' If found the 1 based index is returned, else -1
' NOTE : if keys appear multiple times it is not necessarily
' the first occurence that will be returned
' NOTE 2 : If you need to search in a certain range, take a look at the cSortableSubRange
' meta container adapter. It keeps binary search simpler
Public Function BinarySearch(ByVal objContainer As iSortableContainer, _
ByVal varItem As Variant, _
ByVal objCriterium As iComparer) As Long
Debug.Assert Not (objContainer Is Nothing)
Debug.Assert Not (objCriterium Is Nothing)
Dim
nCount As Long
Dim nHigh As Long
Dim nLow As Long
Dim nTemp As Long
Dim nCurrent As Long
Dim nCOmpRes As Integer
BinarySearch = -1 ' default is not found
nLow = 1 ' containers are assumed one based
nCount = objContainer.Count
nHigh = nCount
nCurrent = (nHigh + nLow) / 2
With objContainer
nCOmpRes = objCriterium.Compare(varItem, .Item(nCurrent))
While nCOmpRes <> 0
If nCOmpRes < 0 Then ' value was smaller than middle so search higher
nLow = nCurrent + 1
Else
If nCOmpRes > 0 Then ' value was bigger so search lower
nHigh = nCurrent - 1
Else
' found but should not be reached
Debug.Assert False
End If
End
If
If nLow > nHigh Then Exit Function ' ------->
nCurrent = (nHigh + nLow) \ 2
nCOmpRes = objCriterium.Compare(varItem, .Item(nCurrent))
Wend
End With
BinarySearch = nCurrent
End Function Is this all there is about searching ?
Well, yes and no. There are only two algorithms I implemented. This immediately explains why I didn’t define an interface for SearchAlgorithm, allthough one day I could. I decided to let my imagination work. Seaching from the back to the front would certainly be a required option, so would searching in a subrange. To accomodate
for this, I defined two new ISortableCOntainer implementations. cSortableFromEnd is a decorator that reverses the perceived order of the decorated SortableContainer. When searching this container, you effectively search from the back to the front. cSortableSubRange is another decorator, which limits the range of the decorate SortableContainer to any subrange. This allows you to search in the first 20 items of an array. To simplify the entire sorting story, I created several facade methods. The most important one is given below :
' FullFeaturedLinearSearch :
' --------------------------
' This search is really just a special case of linear search (where
' you would expect the opposite). Depending on the optional parameters
' we create zero, one or two additional container adapters.
Public Function FullFeaturedLinearSearch(ByVal objContainer As iSortableContainer, _
ByVal varItem As Variant, _
ByVal objCriterium As iComparer, _
Optional ByVal nStartIndex As Long = -1, _
Optional ByVal nEndIndex As Long = -1, _
Optional ByVal bSearchFromEnd As
Boolean = False) As Long
Dim objRevertContainer As cSortableFromEnd
Dim objSubRangeContainer As cSortableSubRange
Dim nResult As Long
Dim bFound As Boolean
If (nStartIndex <> -1) Or (nEndIndex <> -1) Then
' other positions : we need to adapt the container
Set objSubRangeContainer = CreateSubRangeContainer(objContainer, nStartIndex, nEndIndex)
Set objContainer = objSubRangeContainer
End If
If bSearchFromEnd Then
' search from the end : we need to adapt the container (maybe again)
Set objRevertContainer = CreateBackwardContainer(objContainer)
Set objContainer = objRevertContainer
End If
' This is the real work
nResult = LinearSearch(objContainer, varItem, objCriterium)
bFound = nResult <> -1
' now convert the index back again
If Not (objRevertContainer Is Nothing) Then
' we reverted the order : ask the adapter to reinterpret the result
If bFound Then ' only if found
nResult = objRevertContainer.RealPos(nResult)
End If
Set objRevertContainer = Nothing
End If
If Not (objSubRangeContainer Is Nothing) Then
' we searched only on a subrange : ask the adapter to reinterpret the result
If bFound Then ' only if found
nResult = objSubRangeContainer.RealPos(nResult)
End If
Set objSubRangeContainer = Nothing
End If
FullFeaturedLinearSearch = nResult
End Function If you carefully examine the code then you see that the facade method has to deal with a particular problem occurring with the SubRangeContainer. We have to translate a returned index back if it comes from a subrangeContainer (or a SortableFromEnd). ( in fact this little problem made me think
hard about a SerachableContainer with a realIndex property for index conversions) With the facade and the two special decorators, this concludes my little searching component. | 
