|
Dit artikel is gepubliceerd op zondag 31 juli 2011 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 2010 Broncode 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 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 found = (number = numbers(index)) exhausted = (upperbound <= lowerbound) If Not (found OrElse exhausted) Then If number > numbers(index) Then lowerbound = index + 1 Else upperbound = index - 1 End If End If Loop 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 SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
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 ZoekmethodenNet 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 2010 Broncode 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 index = Array.BinarySearch(numbers, number) Dim found As Boolean = index > -1 If found Then Console.WriteLine(number & " found at index " & index) Else Console.WriteLine(number & " not found") End If Next Console.ReadLine() End SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
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  boven
7.3.2. OefeningOpgave :
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 2010 Broncode 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() Console.ReadLine() End SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
Console Application Output Zip Code ?
2000
Antwerp Console Application Output Zip Code ?
4000
City not found. Oplossing : Visual Basic 2010 Broncode 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 SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
boven 7.3.3. Performantie in Big-O-NotationOm 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 zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
| 
6. 
