INF_CHR20_VWO_P6_LES-06

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Algoritmes - Binary Search

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Leerdoelen

Wij gaan het hebben over wat lineaire search is 

Wij gaan het hebben over wat binair search is

Wij gaan het hebben over best, worst en averagecasescenario is

Je kunt berekenen hoeveel stappen je nodig hebt om het goede antwoord te vinden door gebruik te maken van logaritme

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

De Linear search 

O(n)

• Recht toe recht aan.
• elke element langs lopen (sequentieel), tot betreffende element is gevonden
• efficient bij kleine hoeveelheden aan elementen zoeken.
• Elementen hoeven niet geordend te zijn
• notatie bij linear search is              (time complexity)

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

De Binary search 

• Indien nodig eerst elementen ordenen
• Elke keer door midden splitsen 
• Is element <, > of == het te zoeken element
• efficient bij kleine hoeveelheden aan elementen zoeken.
  
• Elementen hoeven niet geordend te zijn
  
• Notatie als geordend :                 (time complexity)
• Als niet geordend :                    (time complexity)

O(log(n))

O(nlog(n))

log2(15)      3

≈

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Best, average, worstcasescenario

Best = in 1 keer het element vinden

average = worstcase / 2 en dan afgerond

worst = in max aantal keren het element vinden

n=15

linear = best 1x, avg 8x, worst 15x

binair = best 1x, avg 2x worst = 3x

Σ

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Opdracht

Maak weekopdracht 6