一维数组中的折半查找算法

    <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