[Year 12 SofDev] Binary search example?

[Travis Parker]

Thanks Chris and Esther - Both very practical examples and they'll
definitely get a run in class!

 

Cheers

 

Trav

 

 

 

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

 

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

 

 

 

 

 

 

 

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/86263b62/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 69035 bytes
Desc: image001.png
Url : http://www.edulists.com.au/pipermail/sofdev/attachments/20110615/86263b62/attachment-0001.png