Binary Search for Classic ASP using VBScript

By Brandon Hunt...
Return to the article Efficiently Searching a Sorted Array

I implemented BinarySearch as a array-neutral function (meaning it's not tied to a specific array) since I've got a couple of different arrays on the page that I needed to use it on.

Parameter descriptions:

searchItem is what you are looking for.
startPos and endPos are starting and ending locations in the array.
aTheList is the array itself.
column refers to the column of the array that you are searching on.

Return value:
It returns the array index where the item was found. Also, the function will return a negative number for an item if it is not found in the array. This value is the negative of the array location where the item would have been if it had actually existed.

Other commentary:
This function only works with whole numbers (I was using it to lookup an ID in a table without having to do a separate select into the database by doing a getrows off a RecordSet object). I have plans to modify it to allow for searching on strings as well (using StrComp), but that's a ways off... :)

FYI, I converted an entire page from standard Recordset / MoveNext style to using GetRows / BinarySearch and dropped to about 25% of the time to output the page (~4 secs to under 1 currently).

If you have any questions, let me know.

Brandon Hunt - brandonh6k@yahoo.com
Return to the article Efficiently Searching a Sorted Array


Function BinarySearch(searchItem, startPos, endPos,
aTheList, column)
	Dim midPoint
	
	If startPos = endPos Then
		If searchItem = aTheList(column, startPos) Then
			BinarySearch = startPos
		Else
			BinarySearch = -(startPos) 'Where it would have been...
		End If
	ElseIf startPos > endPos Then
		BinarySearch = -(startPos)	
	Else
		midPoint = CLng(startPos + ((endPos - startPos) / 2))
		If searchItem = aTheList(column, midPoint) Then
			BinarySearch = midPoint
		Else
			If searchItem < aTheList(column, midPoint) Then
				BinarySearch = BinarySearch(searchItem, startPos, midPoint - 1, aTheList, column)
			Else
				BinarySearch = BinarySearch(searchItem, midPoint + 1, endPos, aTheList, column)
			End If
		End If
	End If		
End Function 'BinarySearch