Nederlands
Menu

Datastructuren en algoritmen

Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?

  1. AHet aantal gegevens moet een macht van twee zijn
  2. BDe gegevens moeten op sleutel gesorteerd zijn
  3. CDe gegevens mogen geen dubbele waarden bevatten
Antwoord en toelichting tonen

Antwoord: B. De gegevens moeten op sleutel gesorteerd zijn

Binair zoeken bepaalt uit de vergelijking met het middelste element of de gezochte waarde in de eerste of de tweede helft ligt, en halveert zo het bereik. Die conclusie klopt alleen omdat de gegevens gesorteerd zijn, dus op een ongesorteerde array werkt binair zoeken niet. Het aantal gegevens hoeft geen macht van twee te zijn; wie het midden kiest als (ondergrens + bovengrens) ÷ 2, naar beneden afgerond, kan elke grootte aan. Dubbele waarden zijn ook geen probleem: een van de gelijke waarden wordt gevonden (de eerste positie vinden vraagt een kleine extra stap).

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?
  2. Binair zoeken zoekt 38 in de oplopende array a[0] tot a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Het zoekbereik begint met lo = 0 en hi = 9, en de middelste positie is (lo + hi) ÷ 2, naar beneden afgerond. Welke reeks geeft, in volgorde, de waarden van de elementen waarmee 38 wordt vergeleken?
  3. De array 5, 3, 8, 1, 4 wordt met bubblesort oplopend gesorteerd. Hoe ziet de array eruit na één doorgang (pass), waarin vanaf het begin tot het eind telkens twee buren worden vergeleken en verwisseld als het linkerelement groter is?
  4. De array 29, 10, 14, 37, 13 wordt met selection sort oplopend gesorteerd: het minimum van het ongesorteerde deel wordt gezocht en verwisseld met het eerste element van het ongesorteerde deel. Hoe ziet de array eruit nadat deze stap twee keer is uitgevoerd?
  5. Een array van 10 elementen wordt met insertion sort oplopend gesorteerd. Elk element vanaf het tweede wordt eruit gehaald en vergeleken met de elementen links ervan, te beginnen bij de linkerbuur, tot een element kleiner dan of gelijk aan de waarde is gevonden of het begin is bereikt. Hoeveel vergelijkingen zijn er nodig als de array al oplopend staat, en als hij aflopend staat?