Wyo VB Lecture Notes

Objective #1: Trace and apply the sequential search algorithm.

• Although there are more efficient ways to search for data, a sequential search is a good choice to use when the amount of data to be searched is small. A sequential search is also called a linear search.
• You simply check each element of an array position by position until you find the one that you are looking for.
• In any search, the item upon which the search is based is called the key
• An advantage to the sequential search is that the algorithm is relatively easy to code.
• The sequential search algorithm's worst case is when the element that you are searching for is the last element in the array or not found in the array. The best case occurs when the element that you are searching for is the very first item in the array.
• A boolean variable can be used to exit early from a loop when the key is found. Also, a boolean value can be returned from a sequential search method to indicate whether or not the target key was found or not. Or, the position within an array where the target is found could be returned.
  
  Dim mintScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim blnFound As Boolean = False
  
     While (Not(blnFound))
        If (mintScores(J) = 33) Then
           blnFound = True
        End If
     End While
  
     If (blnFound) Then
        MessageBox.Show("33 was found")
     Else
        MessageBox.Show("33 was not found")
     End If
  End Sub
  
  
• The following code is a linear search that finds the maximum value in an array.
  
  Dim mintScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim intMax As Integer = 0
  
     For J = 0 To mintScores.Length()
        If (mintScores(J) > intMax) Then
           intMax = mintScores(J)
        End If
     Next
  
     MessageBox.Show(intMax)
  End Sub

Objective #2: Trace and apply the binary search algorithm.

• If the data in an array is already sorted in order (alphabetically for example) then a binary search is much more efficient and usually quicker than a sequential search.
• In the case of a binary search, you first examine the "middle" element in the array. If that element is "lower" (alphabetically, for example) than the element which you are looking for, then you discard the lower half of the data and continue to search the upper half. The process repeats itself when you then look at the middle element of the remaining "upper half" of the data.
• The worst case of a binary search is that you do not find the key but even the worst case doesn't take too long. If the array has 100 elements, then it would take at most 7 loop iterations to find any element in the array since 2 ^ 7 is the first power of two that is greater than 100.
• Here is a version of the binary search algorithm
  
  Dim mintScores() As Integer = {5, 13, 29, 31, 44, 53, 66, 75, 87, 99}
  
  Private Sub btnBinarySearch_Click(...)
     Dim intLow As Integer = 0
     Dim intHigh As Integer = mintScores.Length() - 1
     Dim intKey As Integer = Val(txtKey.Text)
     Dim intMid As Integer = intHigh / 2
     Dim blnFound As Boolean = False

     System.Array.Sort(mintScores)
  
     While (Not (blnFound) And intLow <= intHigh)

        If (mintScores(intMid) = intKey) Then
           blnFound = True
        Else

           If (mintScores(intMid) > intKey) Then
              intHigh = intMid - 1
           ElseIf (intKey > mintScores(intMid)) Then
              intLow = intMid + 1
           End If

           intMid = Math.Round((intLow + intHigh) / 2)
        End If

     End While

     If (blnFound = True) Then
        lblResult.Text = "Found in position " + intMid.ToString()
     Else
        lblResult.Text = "Not Found"
     End If
  
  End Sub