Visual Basic 2012 Voorbeelden
   

visual basic 2012 broncode voorbeelden

Blijf op de hoogte van de recente aanpassingen op vbvoorbeelden!

Microsoft Visual Studio 2012Microsoft Developers Network - Visual BasicMicrosoft .NET Framework

7.3. Binair Zoeken in Arrays

Print Email Deel op Twitter Deel op Facebook

Dit artikel is gepubliceerd op maandag 15 oktober 2012 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

Een intelligentere (en performantere) methode dan het lineair zoeken is het binair zoeken (ook wel logaritmisch zoeken genoemd).

Hierbij is wel vereist (wat niet het geval is voor het lineair zoeken) dat de tabelelementen op een of andere manier gesorteerd zijn.

De methode bestaat erin :

(1) het middelste element van de array te bepalen
(2) te bepalen of de waarde die je zoek dat middelste element is, indien zo kan het zoeken gestaakt worden, indien niet gaat men verder met volgende stappen
(3) controleren of alle elementen doorzocht zijn, indien zo kan het zoeken gestaakt worden, indien niet gaat men verder met volgende stap
(4) bepaal (op basis van de sortering) of de waarde zich in het linker of in het rechterdeel (ten opzichte van het middelste element) bevindt

En herhaal stappen 1, 2, 3 en 4 (voor dat linker- of rechterdeel) totdat de waarde gevonden is, of totdat alle elementen doorzocht zijn.

Om de werkwijze te illustreren veronderstellen we een array met daarin de eerste 10 veelvouden van 5 :
index     0   1   2   3   4   5   6   7   8   9
value     5   10  15  20  25  30  35  40  45  50
De array is gesorteerd dus kunnen we hierop de "binary search" methode gaan toepassen.

Veronderstel dat we van waarde 20 wensen op te zoeken of het zich in de array bevindt, dan kunnen we als volgt te werk gaan :

Zoek-doorloping 1 : (zoek-bereik vanaf index 0 tot en met index 9) :
lowerbound    upperbound    middle index      middle element
0             9             (0 + 9) \ 2 = 4   25
25 is meer dan de waarde die we zoeken (20), dus kunnen we hier concluderen dat gezien de elementen van klein naar groot zijn gesorteerd in de tabel, dat indien 20 zich in de tabel bevindt, dit in het linkerdeel zal zijn (ten opzicht van waarde 25 (of dus element op index 4)).

Om verder te werken met het linkerdeel, stellen we nu gewoon dat de rechtergrens nu net links van de middelste index ligt :

Zoek-doorloping 2 : (zoek-bereik vanaf index 0 tot en met index 3) :
lowerbound (*)   upperbound (*)   middle index      middle element
0                4 - 1 = 3        (0 + 3) \ 2 = 1   10

(*) of the search range
De waarde die we zoeken (20) is groter dan de middelste waarde (10), dus gaan we verder met het rechterdeel, door te veronderstellen dat de linkergrens nu 1 meer is dan het midden :

Zoek-doorloping 3 : (zoek-bereik vanaf index 2 tot en met index 3) :
lowerbound (*)   upperbound (*)   middle index      middle element
1 + 1 = 2        3                (2 + 3) \ 2 = 2   15

(*) of the search range
De waarde van het middelste element (15) is kleiner dan de waarde die we zoeken (20) dus gaan we verder met het rechterdeel :

Zoek-doorloping 4 : (zoek-bereik vanaf index 3 tot en met index 3) :
lowerbound (*)   upperbound (*)   middle index      middle element
2 + 1 = 3        3                (3 + 3) \ 2 = 3   20

(*) of the search range
De waarde van het middelste element (20) is nu ook de waarde die we zochten ( 20), er kan dus nu geconcludeerd worden dat de waarde gevonden is.

Veronderstel dat we waarde 21 zochten (in plaats van 20), dan hadden we tot nu toe identieke zoek-doorlopingen.   21 is echter groter dan 20 (het middelste element) dus zou je verder willen gaan met het rechter deel, maar gezien het zoekbereik (die nu maar 1 element groot meer is) niet meer kan worden opgedeeld, zou hier meteen besloten kunnen worden dat 21 zich niet in de tabel bevindt.
Visual Basic 2012 Broncode - Codevoorbeeld 115
Module BinarySearch
    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
            ' binary search
            upperbound = count - 1
            Dim lowerbound As Integer = 0
            Dim found As Boolean = False
            Dim exhausted As Boolean = False
            Do Until found OrElse exhausted
                index = (lowerbound + upperbound) \ 2                         ' (1)
                found = (number = numbers(index))                             ' (2)
                exhausted = (upperbound <= lowerbound)                        ' (3)
                If Not (found OrElse exhausted) Then
                    If number > numbers(index) Then                           ' (4)
                        lowerbound = index + 1
                    Else
                        upperbound = index - 1
                    End If
                End If
            Loop
            ' output
            If found Then
                Console.Write(number & " found at index " & index)
            Else
                Console.Write(number & " not found")
            End If
            If exhausted Then
                Console.Write(", search exhausted")
            Else
                Console.Write(", search not exhausted")
            End If
            Console.WriteLine(", last searched " & lowerbound & " to " & upperbound)
        Next
        '
        Console.ReadLine()
    End Sub
End Module
Console Application Output
1 not found, search exhausted, last searched 0 to 0
2 found at index 0, search exhausted, last searched 0 to 0
3 not found, search exhausted, last searched 0 to 0
4 found at index 1, search not exhausted, last searched 0 to 3
5 not found, search exhausted, last searched 2 to 1
6 found at index 2, search not exhausted, last searched 2 to 3
7 not found, search exhausted, last searched 3 to 3
8 found at index 3, search exhausted, last searched 3 to 3
9 not found, search exhausted, last searched 3 to 3
10 found at index 4, search not exhausted, last searched 0 to 9
11 not found, search exhausted, last searched 5 to 4
12 found at index 5, search not exhausted, last searched 5 to 6
13 not found, search exhausted, last searched 6 to 6
14 found at index 6, search exhausted, last searched 6 to 6
15 not found, search exhausted, last searched 6 to 6
16 found at index 7, search not exhausted, last searched 5 to 9
17 not found, search exhausted, last searched 8 to 7
18 found at index 8, search not exhausted, last searched 8 to 9
19 not found, search exhausted, last searched 9 to 9
20 found at index 9, search exhausted, last searched 9 to 9
21 not found, search exhausted, last searched 9 to 9
De binary search methode is een stuk efficiënter dan het lineair zoeken gezien je het zoekbereik steeds gaan halveren, dit althans wanneer we zoeken in een "grote" collectie, met "veel" elementen.

Bemerk dat het middelste element min of meer mag bepaald worden, bij een even aantal elementen is er geen exact midden te bepalen.  Zolang je het zoekbereik maar in 2 delen opsplits blijft deze methode functioneren.  En zolang de 2 delen even groot zijn (min of meer, maximum 1 element verschil), blijft de performantie overeind.

Vanaf het zoekbereik slechts één element bevat, en we reeds gezien hadden dat dat ene element niet gelijk is aan de zoekwaarde, kunnen we concluderen dat de waarde zich niet in de tabel bevindt.
Het nagaan of het zoekbereik slechts één element bevat kunnen we doen door de upperbound en de lowerbound te vergelijken.  Als deze gelijk zijn aan elkaar (upperbound = lowerbound) bevat het zoekbereik maar één element.
Toch is in bovenstaand algoritme de conditie iets anders, namelijk upperbound <= lowerbound.  We gaan dus ook na of de upperbound wel niet kleiner is dan de lowerbound.  Op het eerste zicht lijkt dit misschien overbodig, toch is dat in bepaalde gevallen vereist.

Veronderstel volgende tabel, waarin we opzoek gaan naar waarde 1.
index     0   1   2   3   4
value     2   3   4   6   8
De lowerbound is initeel 0, de upperbound 4 en de middelste waarde 4.
lowerbound (*)   upperbound (*)   middle index      middle element
0                4                (0 + 4) \ 2 = 2   4

(*) of the search range
De zoekwaarde 1 is kleiner dan de middelste waarde 4, dus zoeken we verder in het linkerdeel :
lowerbound (*)   upperbound (*)   middle index      middle element
0                2 - 1 = 1        (0 + 1) \ 2 = 0   2

(*) of the search range
De waarde 1 die we zoeken is kleiner dan de middelste waarde 2 en het zoekbereik bevat hier nog twee elementen.
Omdat de zoekwaarde kleiner is dan de middelste waarde verplaatsen we de upperbound :
lowerbound       upperbound
0                0 - 1 = -1
Op dit moment bevat het zoekbereik nul elementen en is de upperbound kleiner dan de lowerbound.  Om dergelijke gevallen op te vangen is de conditie upperbound <= lowerbound.

Om een binary search te kunnen toepassen is vereist dat je zoekt in een gesorteerde tabel.  Deze vereiste is niet van toepassing voor het lineair zoeken, waardoor deze in minder gevallen toepasbaar is.

7.3.1. Voorgedefinieerde Zoekmethoden

Net als voor het lineair zoeken (IndexOf) bestaat er ook voor het binair zoeken een voorgedefinieerde functionaliteit (1).

De shared function BinarySearch van de klasse Array zal in de tabel ( eerste argumentwaarde) de eerste positie van de waarde (tweede argumentwaarde) opleveren.  Wordt de waarde niet gevonden dan levert deze function -1 op.
Visual Basic 2012 Broncode - Codevoorbeeld 116
Module BinarySearch
    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
            ' binary search
            index = Array.BinarySearch(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
Console Application 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

7.3.2. Oefening

Opgave :

Maak een programma dat via de "binary search" methode op basis van een postcode op zoek gaat naar de gerelateerde gemeente.  Maak echter geen gebruik van de voorgedefinieerde zoekmethodes, maar implementeer deze zelf.

Doe dit door onderstaande programma-code te vervolledigen.
Visual Basic 2012 Broncode - Codevoorbeeld 117
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()
        '
        ' ... (binary search) ...
        '
        Console.ReadLine()
    End Sub
End Module
Console Application Output
Zip Code ?
2000
Antwerp
Console Application Output
Zip Code ?
4000
City not found.
Oplossing :
Visual Basic 2012 Broncode - Codevoorbeeld 118
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 lowerbound, index As Integer
        Dim upperbound As Integer = count - 1
        Do Until found OrElse exhausted
            index = (lowerbound + upperbound) \ 2
            found = (zipCode = zipCodes(index))
            exhausted = (upperbound <= lowerbound)
            If Not (found OrElse exhausted) Then
                If zipCode > zipCodes(index) Then
                    lowerbound = index + 1
                Else
                    upperbound = index - 1
                End If
            End If
        Loop
        '
        If found Then
            Console.WriteLine(names(index))
        Else
            Console.WriteLine("City not found.")
        End If
        '
        Console.ReadLine()
    End Sub
End Module

7.3.3. Performantie in Big-O-Notation

Om de performantie van de 2 zoekmethoden nog eens met elkaar te vergelijken zouden we kunnen bekijken wat het maximum aantal zoek-doorlopingen is voor beide technieken.

Bij de linear search (met N = aantal elementen in de array) is dit N, als de waarde die je zoekt zich op de laatste positie bevindt (of zich niet in de tabel bevindt) en je begint van voor naar achter te zoeken, dan zal je dus in het slechtste geval alle elementen moeten doorlopen, of evenveel zoek-doorlopingen hebben als het aantal elementen.

Bij de binair search kan je maximaal evenveel zoek-doorlopingen hebben als het aantal keer je het zoekbereik kan gaan opdelen in 2.
Dus (met R = eerste macht van 2 groter dan N) is het maximum aantal zoekdoorlopingen log2 R (het logaritme van basisgetal 2 op R).  Vandaar ook de naam "logaritmisch" zoeken.  Als we zoals in het voorbeeld 10 elementen hebben, is de eerste macht van 2 groter dan 10 : 16.
Dus log2 16 of dus 4 (2 tot de vierde is 16) is hier het maximum aantal zoekdoorlopingen.  We kunnen immers een zoekbereik van 10 elementen maximaal 4 keer gaan opsplitsen in 2 delen.

Dus maximum aantal zoek-doorlopingen :
- linaer search : N
- binary search : log2 R

Een alternatieve wijze (die regelmatig gebruikt wordt) om de performantie uit te drukken van algoritmes is de "big-O-notatie".  Hierbij probeert men niet het exacte aantal stappen (of dus bijvoorbeeld zoek-doorlopingen) weer te geven, maar wel de manier waarop het aantal stappen groeit op basis van een toename van de input (voorgesteld met N) voor het algoritme.

Stel nu de instructie : "x = x + 1", deze zal een constante tijd duren.  Dit geeft men aan met "O(1)" in de big-O-notatie.

Veronderstel :
For i = 1 to N
    x = x + 1
Next
De instructie ("x = x + 1") waarvan we reeds stelden dat ze een constante tijd duurde wordt hier een proportioneel aantal keer met N (met dus de input) uitgevoerd, je kan hier stellen in big-O-notatie : "O(N)".
Men spreekt in dergelijk geval over een "linear running time".  Er is immers een lineair verband tussen de groei van de input en de groei van tijd die nodig is om dit algoritme uit te voeren.

Veronderstel :
For i = 1 to N
    For j = 1 to N
        x = x + 1
    Next
Next
De instructie wordt hier niet N keer, maar N maal N keer uitgevoerd.
N x N = N^2 of dus in big-O-notatie : "O(N^2)".
Je kan hier spreken over een "quadratic running time".

Omdat in de big-O-notatie men slechts de evolutie van het aantal stappen op basis van de input wenst te definiëren is het best deze evolutie zo eenvoudig mogelijk weer te geven.  Een aantal vereenvoudigingen dienen zich dus aan.

Negeer bijvoorbeeld constante factoren : "O(10 N^2)" is bijvoorbeeld te vereenvoudigen naar "O(N^2)".

Bij "O(10 N^2)" met N = 5 hebben we 10 x 5 x 5 = 250, als we de input 4 maal verhogen (N = 20) krijgen we 10 x 20 x 20 = 4000.
Hierbij kan je stellen dat bij een groei van de input met factor 4, het aantal stappen zal groeien met factor 16.

Bij "O(N^2)" met N = 5 hebben we 5 x 5 = 25, als we de input 4 maal verhogen ( N = 20) krijgen we 20 x 20 = 400.
Ook hier kan je nu stellen dat bij een groei van de input met factor 4, het aantal stappen zal groeien met factor 16.  Logisch ook gezien N^2 met N = 4 dus 4 x 4 of 16 is.

Een andere vereenvoudiging bestaat erin grondtallen van logaritmen weg te laten.  "O(log2 N)" kan vereenvoudigd worden naar "O(log N)".

Laten we even het resultaat voor verschillende grondtallen bepalen ( grondtallen 2 en 4) :

Met N = 1024, bij log2 N = 10 en bij log4 N = 5.
Met N = 4096, bij log2 N = 12 en bij log4 N = 6.

Dus bij een groei van de input met factor 4, zal het aantal stappen steeds groeien met factor 1,2.  Het grondtal is dus onbeduidend, en kan dus ter vereenvoudiging beter worden weggelaten.

Men laat ook wel eens kleinere factoren bij grote input (hoge N waarde) gewoon weg, gezien deze bijna niet relevant zijn (bij hoge N waarde).  "O(N^2 + N)" wordt zo vereenvoudigd naar "O(N^2)".

Met N = 1000, bij N^2 = 1 000 000 en bij N^2 + N = 1 001 000.
Met N = 3000, bij N^2 = 9 000 000 en bij N^2 + N = 9 003 000.

Dus bij een groei van de input met factor 3 is de groei van het aantal stappen ruwweg gesteld 9.  Of dus 3 x 3 of dus ruwweg : "O(N^2)".

De performantie van de zoekmethoden kan in big-O-notatie dus als volgt worden uitgedrukt :
- linear search : "O(N)"
- binary search : "O(log2 N)" of vereenvoudigd dus "O(log N)"

Dit artikel is gepubliceerd op maandag 15 oktober 2012 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.