Visual Basic 2008 9.0 .NET Examples and Ebook

When we need to search for a value in an unsorted collection, we have no other option than check element by element for a match.

This technique is called the linear search technique. We iterate over all elements until we have found the element were looking for or until weve searched the complete collection.

Following example fills an array with the first 10 multiples of base 2.
All values from 1 to 21 are then searched for within the array using a linear search technique.

The search algorithm uses Booleans which indicate whether or not the value is found, and whether or not the complete array was searched. When the search finishes these Booleans can be used to extract the necessary information.
The search algorithm also uses an index variable which is continuously incremented until the value is found, or the complete array is searched.
This index variable can then be used to retrieve the position of the found value.

Module LinearSearch
    Sub Main()
        Dim base As Integer = 2
        Dim count As Integer = 10
        Dim upperbound As Integer = count - 1
        Dim numbers(upperbound) As Integer
        '
        Dim index As Integer
        For index = 0 To upperbound
            numbers(index) = (index + 1) * base
        Next
        '
        Dim number As Integer
        For number = base - 1 To base * count + 1
            ' linear search
            Dim found As Boolean = False
            Dim exhausted As Boolean = False
            index = -1
            Do Until found OrElse exhausted
                index += 1
                found = (numbers(index) = number)
                exhausted = (index = upperbound)
            Loop
            ' output
            If found Then
                Console.Write(number & " found at index " & index)
            Else
                Console.Write(number & " not found")
            End If
            If exhausted Then
                Console.WriteLine(", search exhausted")
            Else
                Console.WriteLine(", search not exhausted")
            End If
        Next
        '
        Console.ReadLine()
    End Sub
End Module

Output :

 1 not found, search exhausted
 2 found at index 0, search not exhausted
 3 not found, search exhausted
 4 found at index 1, search not exhausted
 5 not found, search exhausted
 6 found at index 2, search not exhausted
 7 not found, search exhausted
 8 found at index 3, search not exhausted
 9 not found, search exhausted
 10 found at index 4, search not exhausted
 11 not found, search exhausted
 12 found at index 5, search not exhausted
 13 not found, search exhausted
 14 found at index 6, search not exhausted
 15 not found, search exhausted
 16 found at index 7, search not exhausted
 17 not found, search exhausted
 18 found at index 8, search not exhausted
 19 not found, search exhausted
 20 found at index 9, search exhausted
 21 not found, search exhausted

Task :

Search for the name of a city with a certain zip code.

Use the linear search technique to search for the position of the entered zipcode in the zipCodes array. Then retrieve then name of the city on the corresponding position in the names array.

Module ExerciseTask
    Sub Main()
        Dim count As Integer = 3
        Dim names() As String = {"Brussels", "Antwerp", "Ghent"}
        Dim zipCodes() As Integer = {1000, 2000, 9000}
        '
        Console.WriteLine("Zip Code ?")
        Dim zipCode As String = Console.ReadLine()
        '
        ' ... (linear search) ...
        '
        Console.ReadLine()
    End Sub
End Module

Output :

 Zip Code ?
 2000
 Antwerp

Output :

 Zip Code ?
 4000
 City not found.

Solution :

Module ExerciseSolution
    Sub Main()
        Dim count As Integer = 3
        Dim names() As String = {"Brussels", "Antwerp", "Ghent"}
        Dim zipCodes() As Integer = {1000, 2000, 9000}
        '
        Console.WriteLine("Zip Code ?")
        Dim zipCode As String = Console.ReadLine()
        '
        Dim found, exhausted As Boolean
        Dim index As Integer = -1
        Do Until found OrElse exhausted
            index += 1
            found = (zipCodes(index) = zipCode)
            exhausted = (index = count - 1)
        Loop
        '
        If found Then
            Console.WriteLine(names(index))
        Else
            Console.WriteLine("City not found.")
        End If
        '
        Console.ReadLine()
    End Sub
End Module

In stead of manually coding a search algorithm, a predefined search method can be used to search for a value in an one-dimensional array.

For instance the shared method IndexOf of class Array (1) can be used to retrieve the position ( the index ) of the searchvalue ( second argument ) within the one-dimensional array ( first argument ).
If the value is not found, IndexOf will return -1.

Module IndexOf
    Sub Main()
        Dim base As Integer = 2
        Dim count As Integer = 10
        Dim upperbound As Integer = count - 1
        Dim numbers(upperbound) As Integer
        '
        Dim index As Integer
        For index = 0 To upperbound
            numbers(index) = (index + 1) * base
        Next
        '
        Dim number As Integer
        For number = base - 1 To base * count + 1
            index = Array.IndexOf(numbers, number)                         ' (1)
            Dim found As Boolean = index > -1
            ' output
            If found Then
                Console.WriteLine(number & " found at index " & index)
            Else
                Console.WriteLine(number & " not found")
            End If
        Next
        '
        Console.ReadLine()
    End Sub
End Module

Output :

 1 not found
 2 found at index 0
 3 not found
 4 found at index 1
 5 not found
 6 found at index 2
 7 not found
 8 found at index 3
 9 not found
 10 found at index 4
 11 not found
 12 found at index 5
 13 not found
 14 found at index 6
 15 not found
 16 found at index 7
 17 not found
 18 found at index 8
 19 not found
 20 found at index 9
 21 not found