I see this homework question asked quite a bit, so I figured I'd post a link to a working example. The assignment is to create a program to add/delete/search for somebody with their phone number. The method I use utilizes a dictionary and LINQ:

Code:
Option Strict On
Option Explicit On
Module Module1

    Private contact As Dictionary(Of String, String)
    Sub Main()
        contact = New Dictionary(Of String, String)

        Call MainMenu()
    End Sub

    Private Function ValidateNumber(ByVal number As String) As Boolean
        If number.Length = 12 AndAlso _
            Integer.TryParse(number.Substring(0, 3), New Integer) AndAlso _
            Integer.TryParse(number.Substring(4, 3), New Integer) AndAlso _
            Integer.TryParse(number.Substring(8), New Integer) Then
            Return True
        Else
            Return False
        End If
    End Function

    Private Sub MainMenu()
        Do
            Console.Clear()

            Console.WriteLine("Search - 1")
            Console.WriteLine("Add    - 2")
            Console.WriteLine("Delete - 3")
            Console.Write("Enter in a selection: ")

            Dim response As String = Console.ReadLine
            Dim result As Integer

            If Integer.TryParse(response, result) AndAlso result > 0 AndAlso result < 4 Then
                Select Case result
                    Case 1
                        Call Search()
                    Case 2
                        Call Add()
                    Case 3
                        Call Delete()
                End Select
            End If
        Loop
    End Sub

    Private Sub Search()
        Do

            Console.Clear()
            Console.ForegroundColor = ConsoleColor.Cyan
            Console.WriteLine("You may return to the main menu at anytime by entering in 'exit'")
            Console.ForegroundColor = ConsoleColor.Gray
            Console.WriteLine()
            Console.Write("Contact's Name: ")

            Dim name As String = Console.ReadLine
            If name.ToLower = "exit" Then
                Exit Do
            End If

            Dim results() As String = Array.FindAll(contact.Keys.ToArray, Function(n) n.ToString.ToLower.StartsWith(name))
            Array.Sort(results)

            If results.Length > 0 Then
                For Each person As String In results
                    Console.WriteLine("     " & person & ": " & contact(person))
                Next
            Else
                Console.WriteLine("No matches found.")
            End If

            Console.WriteLine()
            Console.WriteLine("Press any key to go back to the search menu.")
            Console.ReadKey()

        Loop
    End Sub

    Private Sub Add()
        Do

            Console.Clear()
            Console.ForegroundColor = ConsoleColor.Cyan
            Console.WriteLine("You may return to the main menu at anytime by entering in 'exit'")
            Console.ForegroundColor = ConsoleColor.Gray
            Console.WriteLine()
            Console.Write("Contact's Name: ")

            Dim name As String = Console.ReadLine
            If name.ToLower = "exit" Then
                Exit Do
            End If

            Dim number As String
            Do
                Console.CursorLeft = 0
                Console.Write("Contact's Number(123-456-7890): ")
                number = Console.ReadLine

                If number.ToLower = "exit" Then
                    Exit Sub
                ElseIf ValidateNumber(number) Then
                    Exit Do
                Else
                    Console.WriteLine("Invalid number. Press any key to re-enter the number.")
                    Console.ReadKey()
                End If
            Loop

            If contact.ContainsKey(name) Then
                Console.WriteLine("There is already a person named " & name & " saved.")
                Console.WriteLine("Press any key to go back to the add menu.")
                Console.ReadKey()
            Else
                contact.Add(name, number)
                Console.WriteLine(name & " was successfully added.")
                Console.WriteLine("Press any key to go back to the add menu.")
                Console.ReadKey()
            End If

        Loop
    End Sub

    Private Sub Delete()
        Do

            Console.Clear()
            Console.ForegroundColor = ConsoleColor.Cyan
            Console.WriteLine("You may return to the main menu at anytime by entering in 'exit'")
            Console.ForegroundColor = ConsoleColor.Gray
            Console.WriteLine()
            Console.Write("Contact's Name: ")

            Dim name As String = Console.ReadLine
            If name.ToLower = "exit" Then
                Exit Do
            End If

            If contact.ContainsKey(name) Then
                contact.Remove(name)
                Console.WriteLine(name & " was successfully removed.")
                Console.WriteLine("Press any key to go back to the delete menu.")
                Console.ReadKey()
            Else
                Console.WriteLine("Could not find a person named " & name)
                Console.WriteLine("Press any key to go back to the add menu.")
                Console.ReadKey()
            End If

        Loop

    End Sub

End Module