[Year 12 SofDev] Binary search example?

[BUCKNELL, Chris]

Hi Trav,

Try this on for size, it is based on code from the book "Data Structures and Algorithms Using Visual Basic.NET" by Michael McMillan

Regards Chris


[cid:image001.png at 01CC2B72.39F67120]




Module Module1
    Const ARRAY_SIZE As Integer = 9 'i.e. 10 item can be stored in the array - VB.NET has zero indexed arrays
    Dim arr(ARRAY_SIZE) As Integer

    Sub Main()
        'Fill array with random numbers
        For index As Integer = 0 To ARRAY_SIZE
            arr(index) = (CInt(Int(100 * Rnd() + 1)))
        Next
        'Sort array
        SelectionSort()
        'Show sorted array
        showArray()

        'Find number 77 in array using standard Binary Search
        Dim position As Integer = binSearch(77)
        If (position > -1) Then
            Console.WriteLine("77 found at position " & position.ToString)
        Else
            Console.WriteLine("Not in the array.")
        End If

        'Find number 77 in array using standard Binary Search
        position = RecursiveBinSearch(77, 0, ARRAY_SIZE)
        If (position > -1) Then
            Console.WriteLine("77 found at position " & position.ToString)
        Else
            Console.WriteLine("Not in the array.")
        End If
        Console.Read()

    End Sub

    Public Function binSearch(ByVal value As Integer) As Integer
        Dim upperBound, lowerBound, mid As Integer
        upperBound = ARRAY_SIZE 'arr.GetUpperBound(0)
        lowerBound = 0
        While (lowerBound <= upperBound)
            mid = (upperBound + lowerBound) \ 2
            If (arr(mid) = value) Then
                Return mid
            ElseIf (value < arr(mid)) Then
                upperBound = mid - 1
            Else
                lowerBound = mid + 1
            End If
        End While
        Return -1
    End Function

    Public Function RecursiveBinSearch(ByVal value As Integer, ByVal lower As Integer, ByVal upper As Integer) As Integer
        If (lower > upper) Then
            Return -1
        Else
            Dim mid As Integer
            mid = (upper + lower) \ 2
            If (value < arr(mid)) Then
                RecursiveBinSearch(value, lower, mid - 1)
            ElseIf (value = arr(mid)) Then
                Return mid
            Else
                Return RecursiveBinSearch(value, mid + 1, upper)
            End If
        End If
    End Function

    Public Sub SelectionSort()
        Dim outer, inner, min, temp As Integer
        For outer = 0 To ARRAY_SIZE - 1
            min = outer
            For inner = outer + 1 To ARRAY_SIZE
                If (arr(inner) < arr(min)) Then
                    min = inner
                End If
            Next
            temp = arr(outer)
            arr(outer) = arr(min)
            arr(min) = temp
        Next
    End Sub

    Public Sub showArray()
        Dim index As Integer
        For index = 0 To ARRAY_SIZE
            Console.Write(arr(index) & " ")
        Next
        Console.WriteLine()
    End Sub

End Module


From: sofdev-bounces at edulists.com.au [mailto:sofdev-bounces at edulists.com.au] On Behalf Of Travis Parker
Sent: Wednesday, 15 June 2011 2:47 PM
To: Year 12 Software Development Teachers' Mailing List
Subject: [Year 12 SofDev] Binary search example?

Dear All,

I was just wondering if anyone has a VB program (Using dot net 2010) that uses a binary search? I would ideally like to give the class a simple program to demonstrate it in action, and rather than write one from scratch during the exam/reporting time - I'm sure one of my more learned colleagues would have one lying around!

Cheers

Trav


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20110615/7e7b7740/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 69035 bytes
Desc: image001.png
Url : http://www.edulists.com.au/pipermail/sofdev/attachments/20110615/7e7b7740/image001-0001.png