<p>一维数组中的折半查找算法的ASP实现。</p>
折半查找是在排好序的数组中可采用的一种非常快的查找方法。它的工作原理如下:
将要查找的数据项与数组的中间元素相比较。
如果它们相同,那么查找成功。
如果查找的数据项小于数组的中间元素,那么就放弃数组的后半部分。
如果查找的数据项大于数组的中间元素,那么就放弃数组的前半部分。
重复步骤1~4,将数组不断减半,直至找到查找的数据项或者查找完整个数组为止。
从下面的程序清单可以看出,折半查找算法在实际应用中几乎不受数组大小的影响,即使数组的长度增加一倍,也只是在程序中多了一次循环而已。
' ' Description: Module containing various binary search routines ' ' Authors: Stephen Bullen, www.oaltd.co.uk ' Rob Bovey, www.appspro.com 'Option Explicit Option Private Module
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ' Comments: Uses a binary search algorithm to quickly locate a string ' within a sorted array of strings ' ' Arguments: sLookFor The string to search for in the array ' auArray An array of strings, sorted in ascending order ' lCompareMethod Either vbBinaryCompare or vbTextCompare. Defaults to vbTextCompare ' lNotFound The value to return if the text isn't found. Defaults to -1 ' ' Returns: Long The located position in the array, or -1 if not found ' ' Date Developer Action ' -------------------------------------------------------------- ' 02 Jun 04 Stephen Bullen Created ' Function BinarySearchString(ByRef sLookFor As String, ByRef asArray() As String, _ Optional ByVal lCompareMethod As VbCompareMethod = vbTextCompare, _ Optional ByVal lNotFound As Long = -1) As Long
Dim lLow As Long, lMid As Long, lHigh As Long Dim iComp As Integer
On Error GoTo PTR_Exit
'Assume we didn't find it BinarySearchString = lNotFound
'Get the starting positions lLow = LBound(asArray) lHigh = UBound(asArray)
Do 'Find the midpoint of the array lMid = (lLow + lHigh) \ 2
'Compare the mid-point element to the string being searched for iComp = StrComp(asArray(lMid), sLookFor, lCompareMethod)
If iComp = 0 Then 'We found it, so return the location and quit BinarySearchString = lMid Exit Do
ElseIf iComp = 1 Then 'The midpoint item is bigger than us - throw away the top half lHigh = lMid - 1 Else 'The midpoint item is smaller than us - throw away the bottom half lLow = lMid + 1 End If
'Continue until our pointers cross Loop Until lLow > lHigh
PTR_Exit:
End Function
'******************************************************************** '* Function Name: BinarySearchVariant '* '* Inputs: vLookFor - The value to search for in the array '* vaArray - A Variant array, sorted in ascending order '* lNotFound - The value to return if the text isn't found '* Defaults to -1 '* '* Outputs: The located position in the array, or -1 if not found '* '* Purpose: Uses a binary search algorithm to quickly locate a string '* within a sorted array of strings '* '******************************************************************** Function BinarySearchVariant(ByVal vLookFor As Variant, ByRef vaArray As Variant, _ Optional ByVal lNotFound As Long = -1) As Long
Dim lLow As Long, lMid As Long, lHigh As Long
On Error GoTo PTR_Exit
'Assume we didn't find it BinarySearchVariant = lNotFound
'Get the starting positions lLow = LBound(vaArray) lHigh = UBound(vaArray)
Do 'Find the midpoint of the array lMid = (lLow + lHigh) \ 2
If vaArray(lMid) = vLookFor Then 'We found it, so return the location and quit BinarySearchVariant = lMid Exit Do
ElseIf vaArray(lMid) > vLookFor Then 'The midpoint item is bigger than us - throw away the top half lHigh = lMid - 1 Else 'The midpoint item is smaller than us - throw away the bottom half lLow = lMid + 1 End If
'Continue until our pointers cross Loop Until lLow > lHigh
PTR_Exit:
End Function