Nederlands
Menu

Wat is Binair zoeken (binary search)?

Zoekmethode voor gesorteerde gegevens die de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert. Ze vindt een waarde tussen n gegevens in hoogstens ⌊log₂ n⌋ + 1 vergelijkingen, dus haar complexiteit is O(log n). De gegevens moeten gesorteerd zijn.

Japanse benaming: 二分探索

“Binair zoeken (binary search)” komt voor in 7 oefenvragen uit 3 onderwerpen, bijv. Datastructuren en algoritmen, A/D- en D/A-conversie, Softwareontwikkeling en projectmanagement.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Binair zoeken (binary search)

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).

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?

  1. A10
  2. B32
  3. C500
Antwoord en toelichting tonen

Antwoord: A. 10

Elke vergelijking halveert het zoekbereik ongeveer, en 2¹⁰ = 1024 ≥ 1000, dus na hoogstens 10 vergelijkingen is het bereik op (⌊log₂ 1000⌋ + 1 = 10). De tijdcomplexiteit is O(log n), en zelfs voor 1 miljoen waarden zijn hoogstens 20 vergelijkingen nodig. 32 komt overeen met √1000 ≈ 31,6, en 500 ligt dicht bij het gemiddelde van lineair zoeken (ongeveer n/2). Bedenk wel dat binair zoeken gesorteerde gegevens vereist en dat het sorteren zelf O(n log n) kost.

“Binair zoeken (binary search)” in de toelichting

Vragen met “Binair zoeken (binary search)” (7)

  1. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  2. 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?
  3. 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?
  4. Na een firmwareversie waarvan bekend is dat ze correct werkt, volgen 1000 commits, en de laatste commit bevat een bug. De bug is door één commit geïntroduceerd en treedt op in elke commit daarna. Hoe vaak moet de firmware maximaal worden gebouwd en getest als de schuldige commit met binair zoeken wordt opgespoord, zoals met git bisect?
  5. Welke uitspraak over de werking van een successive-approximation-ADC (SAR-ADC) is juist?
  6. Hoeveel vergelijkingen voert een N-bits successive-approximation-AD-converter in principe uit per conversie?
  7. Lineair zoeken vergelijkt de elementen van een array met 100 verschillende waarden één voor één vanaf het begin om een gezochte waarde te vinden. De gezochte waarde staat altijd in de array en heeft op elke positie dezelfde kans. Wat is het gemiddelde aantal vergelijkingen?

Verwante termen

Array Tijdcomplexiteit (O-notatie) SAR-ADC (successive approximation) Git Comparator Oversampling ΔΣ-ADC (delta-sigma-ADC) Algoritme van Dijkstra Binaire heap (binary heap) Binaire zoekboom (binary search tree)

Naar de woordenlijst