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:

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