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 (aka linear search) is a good choice to use when the amount of data to be searched is small. 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 that you are looking for is called the key
  
  
• An advantage to the sequential search is that the algorithm is easy to code.
  
  
• Here is an example of a sequential search that looks for the key value 28 in an array
  
  Dim mScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
  
     For J = 0 To mScores.Length - 1
  
        If (mScores(J) = 28) Then
           MessageBox.Show("28 was found")
        End If
  
     Next
  
  End Sub
  
  Note that mScores.Length - 1 is used as the upper boundary for the For loop. To allow the code to be more easily updated in the future, especially if the length of the array changes, do not hard-wire the upper boundary to the number 4.
  
  
• 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 mScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim found As Boolean = False
  
     While (Not(found))
  
        If (mScores(J) = 33) Then
           found = True
        End If
  
     End While
  
     If (found) Then
        MessageBox.Show("33 was found")
     Else
        MessageBox.Show("33 was not found")
     End If
  
  End Sub
  
  
• The following code is a sequential search that finds the maximum value in an array.
  
  Dim mScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim max As Integer = 0
  
     For J = 0 To mScores.Length() - 1
        
        If (mScores(J) > max) Then
           max = mScores(J)
        End If
  
     Next
  
     MessageBox.Show(max)
  End Sub
  
  Notice that the upper boundary of the loop is mScores.Length() - 1 rather than the hard-wired value 4.
  
  The algorithm is more efficient by initializing max to mScores(0) and starting the loop variable J at 1 rather than 0
  
  Dim mScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim max As Integer = mScores(0)
  
     For J = 1 To mScores.Length() - 1
  
        If (mScores(J) > max) Then
           max = mScores(J)
        End If
  
     Next
  
     MessageBox.Show("The max value is " + max)
  End Sub
  
  You can keep track of the position where you find the maximum value by using an additional variable like positionOfMax as in the example below
  
  Dim mScores() As Integer = {32, 45, 28, 99, 70}
  
  Private Sub btnFind_Click(...)
     Dim J As Integer = 0
     Dim max As Integer = mScores(0)
     Dim positionOfMax As Integer = 0
  
     For J = 1 To mScores.Length() - 1
  
        If (mScores(J) > max) Then
           max = mScores(J)
           positionOfMax = J
        End If
  
     Next
  
     MessageBox.Show("The max value " + max + " was found in position " + positionOfMax)
  End Sub
  
  
• 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.

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 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. While you will not have to write this algorithm from scratch, you should be able to fill in the blanks if it is given to you as a quiz or on a test.
  
  Dim mScores() As Integer = {5, 13, 29, 31, 44, 53, 66, 75, 87, 99}
  
  Private Sub btnBinarySearch_Click(...)
     Dim low As Integer = 0
     Dim high As Integer = mScores.Length() - 1
     Dim key As Integer = Val(txtKey.Text)
     Dim mid As Integer = high / 2
     Dim found As Boolean = False

     System.Array.Sort(mScores)     ' array must be sorted in order for binary search to work
  
     While (Not (found) And low <= high)

        If (mScores(mid) = key) Then
           found = True
        Else

           If (mScores(mid) > key) Then
              high = mid - 1
           ElseIf (mScores(mid) < key) Then
              low = mid + 1
           End If

           mid = Math.Round((low + high) / 2)
        End If

     End While

     If (found = True) Then
        lblResult.Text = "Found in position " + Str(mid)
     Else
        lblResult.Text = "Not Found"
     End If
  
  End Sub