Binary Search Of Sorted Array Table
For a complete description of arrays, see Arrays
Searching Array Tables is a useful practice for quick delivery of "translations". For example, the "Searched For" array could contain 2,000 entries, each entry containing a zip-code. The "Resultant' array would also contain 2,000 entries, but each entry would contain the City name corresponding to the zip code.
The programmer would use the zip code as a search argument, and the binary search would return the city name.
The code below follows a good practice when using a binary search - ALWAYS sequence check the array being searched. Arrays that are not in ASCII order will create erroneous results when a binary search is used.
Program Code
Option Explicit
Option Base 1
Sub TestBinarySearch()
' ********************************************************
' strSearchArray Contains the Sorted Values Being Searched
' ********************************************************
Dim strSearchArray(15) As String
' ********************************************************
' strValueArray Contains the Value Resulting Value
' Corresponding To The "Searched For" Value
' ********************************************************
Dim strValueArray(15) As String
' ********************************************************
' The Maximum Array Entries
' ********************************************************
Dim lngTheUpperLimit As Long
' ********************************************************
' The "Searched For" Argument
' ********************************************************
Dim strTheSearchFor As String
' ********************************************************
' The Result of the Search - True Or False (Found or Not)
' ********************************************************
Dim booFound As Boolean
' ********************************************************
' The Resulting Value When The Search Argument is Found
' ********************************************************
Dim strFoundValue As String
' ********************************************************
' To Make Certain The Search Array Is In Sequence
' ********************************************************
Dim booOutOfSequence As Boolean
' ********************************************************
' Initialize Test Data Arrays
' ********************************************************
strSearchArray(1) = "A"
strSearchArray(2) = "C"
strSearchArray(3) = "E"
strSearchArray(4) = "G"
strSearchArray(5) = "I"
strSearchArray(6) = "K"
strSearchArray(7) = "M"
strSearchArray(8) = "P"
strSearchArray(9) = "R"
strSearchArray(10) = "T"
strSearchArray(11) = "V"
strSearchArray(12) = "W"
strSearchArray(13) = "X"
strSearchArray(14) = "Y"
strSearchArray(15) = "Z"
strValueArray(1) = "1"
strValueArray(2) = "2"
strValueArray(3) = "3"
strValueArray(4) = "4"
strValueArray(5) = "5"
strValueArray(6) = "6"
strValueArray(7) = "7"
strValueArray(8) = "8"
strValueArray(9) = "9"
strValueArray(10) = "10"
strValueArray(11) = "11"
strValueArray(12) = "12"
strValueArray(13) = "13"
strValueArray(14) = "14"
strValueArray(15) = "15"
' ********************************************************
' Sequence Check the Search Array
' ********************************************************
Call Sequence_Check(strSearchArray, 15, booOutOfSequence)
' ********************************************************
' Loop Through The Test Until The User Enters "Exit"
' ********************************************************
Do Until strTheSearchFor = "Exit"
strTheSearchFor = InputBox("Enter Search Argument")
lngTheUpperLimit = 15&
strFoundValue = "*"
Call BinarySearch(strSearchArray, strValueArray, lngTheUpperLimit, strTheSearchFor, booFound, strFoundValue)
MsgBox ("Found = " & booFound & " Value = " & strFoundValue)
Loop
End Sub
Sub BinarySearch(SearchArray() As String, _
ValueArray() As String, _
UpperLimit As Long, _
SearchFor As String, _
Found As Boolean, _
FoundValue As String)
Dim Left As Long
Dim Right As Long
Dim Middle As Long
' ********************************************************
' Initialize Variables For The Start of the Search
' ********************************************************
Found = False
Left = 1&
Right = UpperLimit
' ********************************************************
' Loop Until Found (Exit Do If Not Found)
' ********************************************************
Do Until Found
If Left > Right Then
Exit Do
End If
Middle = (Left + Right) / 2&
If SearchArray(Middle) = SearchFor Then
Found = True
FoundValue = ValueArray(Middle)
ElseIf SearchFor > SearchArray(Middle) Then
Left = Middle + 1&
Else
Right = Middle - 1&
End If
Loop
End Sub
Sub Sequence_Check(SearchArray() As String, UpperLimit As Long, OutOfSequence As Boolean)
Dim strLastSearchValue As String
Dim i As Long
' ********************************************************
' Initialize Sequence Check Variables
' ********************************************************
OutOfSequence = False
If UpperLimit < 2& Then
Exit Sub
End If
' ********************************************************
' Sequence Check The Search Array
' ********************************************************
strLastSearchValue = SearchArray(1)
For i = 2& To UpperLimit
If SearchArray(i) < strLastSearchValue Then
OutOfSequence = True
Exit Sub
Else
strLastSearchValue = SearchArray(i)
End If
Next i
End Sub