<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