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

一维数组中的折半查找算法的ASP实现。

折半查找是在排好序的数组中可采用的一种非常快的查找方法。它的工作原理如下: 

将要查找的数据项与数组的中间元素相比较。 
如果它们相同,那么查找成功。 
如果查找的数据项小于数组的中间元素,那么就放弃数组的后半部分。 
如果查找的数据项大于数组的中间元素,那么就放弃数组的前半部分。 
重复步骤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 

Add comment

Loading