Samenvatting Datastructuren deel 1

Datastructuren: Samenvatting deel 1
Binary search
Wat is zoeken?
Een datastructuur slaat data op. De simpelste vorm van een datastructuur is een List (in C#), die
elementen van verschillende datasoorten kan opslaan (integers, strings, tupels, enz.).

Databases: je bemoeit je niet met de details van de opslag, maar je stopt vragen die je “aan de data wilt
stellen” in de SQL-query.

Datastructuren: je zoekt naar de beste organisatie van je data, rekening houdend met de vragen die je
wil stellen

Zoeken door een ongesorteerde lijst
Je wil een element x zoeken in een ongesorteerde rij. Dit is niet moeilijk om te implementeren, maar het
zoeken zelf kan erg tijdrovend zijn, want je moet door de hele lijst heen totdat je het element x vindt.
Toevoegen aan de lijst is echter wel heel makkelijk, je plakt het element gewoon op de eerste open plek.

Lineaire tijd O(n): de zoektijd is evenredig met het aantal elementen

Ongesorteerd → toevoegen is goedkoop, zoeken is duur

Zoeken door een gesorteerde lijst
Je wil een element x zoeken in een gesorteerde rij, waarin de elementen van groot naar klein staan.
Toevoegen is nu duur geworden, want we moeten zoeken waar het element dat we willen toevoegen past
(weer lineaire tijd).

Het zoeken gaat nu echter een stuk sneller; we bekijken het element in het midden van de lijst, en als dat
element groter is, dan x moeten we links van dat element verder zoeken en als het kleiner is, zoeken we
verder rechts. Door één element te bekijken, kunnen we de helft van de lijst uitsluiten. Door dit meerdere
keren te herhalen komen we snel uit bij element x.

Gesorteerd → toevoegen is duur, zoeken is goedkoop


Binary search
Het idee van binary search is als volgt:

Houd twee variabelen bij: de onder- en bovengrens van je zoekgebied (i en j)

Bekijk het middelste element en bepaal of je links of rechts van dat element verder gaat zoeken (m =
(i+j)/2)

Pas op basis daarvan je boven- of ondergrens aan

Kleiner dan m → links zoeken + pas je bovengrens aan (j = m)

Groter dan m → rechts zoeken + pas je ondergrens aan (i = m)

Stop als je gebied klein genoeg is (wanneer je je waarde gevonden hebt)




Datastructuren: Samenvatting deel 1 1

, De invariant
Het maken van een loop is ingewikkeld omdat de vier factoren die de loop omschrijven elkaar allemaal
beïnvloeden. De vier elementen zijn:

Initialisatie I: welke variabelen gebruik je en hoe krijgen ze hun initiële waarde

Conditie C: wanneer stop je de loop

Body B: wat ga je in de loop doen

Terminatie T: hoe ga je verder als de loop klaar is

Om dingen aan te passen zonder dat andere elementen ook aangepast worden gebruik je de invariant.
Deze zorgt ervoor dat je met minder dingen tegelijk rekening hoeft te houden.

Invariant: een predikaat over je variabelen en je data, waarvoor je zorgt dat die waar is voor en na elke
ronde van de loop

Bij het kiezen van de invariant formule P moet je rekening houden met de volgende punten:

De initialisatie moet zorgen dat na de initialisatie de formule P geldt (waar is), om dit aan te tonen mag
je de gegevens gebruiken

De body moet zo geschreven zijn zodat P zowel voor als na de body geldt (waar is)

De conditie kun je zo kiezen dat je uit ¬C ∧ P een logische conclusie kan trekken over dat wat je wil
weten

P omdat die na elke ronde van de loop moet gelden

¬C omdat C de terminatie conditie is

Gebruik ¬C ∧ P om je uitkomst te bepalen
Partieel correct: variant
Een programma dat niet termineert (vanwege een lege of incomplete body) voldoet niet aan de premisse
en dan is dus aan partiële correctheid voldaan (je voldoet aan de variant, maar je krijgt nooit een output).
Om te zorgen dat er wel een terminatie is, moet je ook zorgen dat er een bepaalde grootheid is die in elke
ronde van de loop daalt. Deze grootheid is de variant.


Voorbeeld: de kleinste doos
Gegeven: een oplopende rij A met n getallen en een element x
Gevraagd: de locatie van element x in A → A[i] = x (als x meerdere keren voorkomt, willen we het eerste
voorkomen van x)
De invariant die we in deze situatie gebruiken is: A[i] < x ∧ A[j] ≥ x
→ j is net als i een positie van een element in de lijst
→ Hiermee zeggen we dus; x ligt in een bepaald gebied, waarbij het groter is dan element i en kleiner
of gelijk aan element j en we gaan dus alleen in dat gebied zoeken, anders geldt de invariant niet

We zoeken dus een j zodat geldt: A[j] ≥ x en A[j-1] < x → je pakje past in doos j, en doos j-1 is net te
klein




Datastructuren: Samenvatting deel 1 2

, Het programma dat dit probleem oplost ziet er als volgt uit:


static int Zoek(x)
{
//Initialisatie:
int i = -1; int j = A.Count();
//Loop:
while(i < j-1)
{
int m = (i + j)/2; //het element in het midden van het zoekgebied
if(A[m] < x) //ga links zoeken van m...
i = m; //... en pas dus de bovengrens aan
else //ga rechts zoeken van m...
j = m; //... en pas dus de ondergrens aan
}
return j
}




De variant in dit programma is de grootte van de zoekruimte, gegeven door j-i. Elke ronde wordt de
waarde van i groter of de waarde van j kleiner, waardoor dus de grootte van de zoekruimte afneemt.


Binair zoeken werk heel snel!
Het aantal rondes in een loop die werkt met binary search is ongeveer lg(n). Dit wordt ook wel de
logaritmische tijd genoemd, oftewel O(lg n).
→ lg(x) is gelijk aan 2_log(x)

Early stopping: NIET DOEN!
Early stopping: als je op plek m precies vind wat je zoekt, kan je ervoor kiezen om te stoppen met
zoeken
Dit is niet aan te raden, early stopping zijn moeilijker om te implementeren en werkt over het algemeen
niet sneller dan binary search. Je bekijkt bovendien elke waarde twee keer; een keer om te kijken of het
de waarde is die je zoekt en dan nog een keer om je zoekgebied te verkleinen.




Datastructuren: Samenvatting deel 1 3