Vergelijkingen
Nog mogelijk
Nodig bij lineair zoeken

  • Doel
  • Nog mogelijk
  • Vergeleken
  • Uitgesloten
  • Gevonden

Meer over binair zoeken

Binair zoeken

Binair zoeken vindt een waarde in een gesorteerde lijst door steeds in het midden te kijken. Is de middelste waarde te klein, dan kan de gezochte waarde alleen erna komen; is ze te groot, alleen ervoor. Hoe dan ook valt de helft van wat er over is af. Kies de waarde om te zoeken, loop stap voor stap door het zoeken, en zie het gearceerde deel krimpen tot de waarde gevonden is of er niets meer over is. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om per stap te gaan. Sleep de stappenschuif om ergens naartoe te springen. De streepjeslijn geeft de waarde aan die je zoekt, en het gearceerde deel is waar die nog kan staan. Binair zoeken heeft een gesorteerde lijst nodig, dus een ongesorteerde lijst wordt eerst gesorteerd. Kies de waarde, hoeveel staven, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies de waarde om naar te zoeken, en hoeveel staven. Of typ je eigen getallen: binair zoeken sorteert ze eerst.
  2. Druk op Afspelen, of gebruik Stap en Terug om per stap te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
  3. Vergelijk de tegel Vergelijkingen met Nodig bij lineair zoeken, voor een waarde aan het eind of een die ontbreekt.

Hoe binair zoeken werkt

Houd bij in welk deel van de gesorteerde lijst de gezochte waarde nog kan staan; eerst is dat de hele lijst. Kijk naar de waarde in het midden ervan. Is die gelijk aan de gezochte waarde, dan ben je klaar. Is ze kleiner, dan kan de gezochte waarde alleen erna komen, dus ga verder met het deel na het midden. Is ze groter, ga dan verder met het deel ervoor. Als er niets meer over is, staat de gezochte waarde niet in de lijst.

Waarom het zo snel is

Elke vergelijking halveert het deel dat er over is. Begin je met n waarden, dan zijn er na k vergelijkingen hoogstens ongeveer n/2ᵏ over, dus het zoeken eindigt na hoogstens ⌊log₂ n⌋ + 1 vergelijkingen: 6 voor 40 waarden, 10 voor 1.000, 20 voor een miljoen. Lineair zoeken moet misschien naar elke waarde kijken. Het addertje: de lijst moet gesorteerd zijn, en hem gesorteerd houden, of eerst sorteren, kost ook iets.

Veelgestelde vragen

Hoe werkt binair zoeken?

Het vergelijkt de gezochte waarde met de middelste waarde van het deel van een gesorteerde lijst waar die nog kan staan. Gelijk betekent gevonden; anders valt de helft af waar de waarde niet kan staan, en gaat het zoeken verder in de andere helft tot de waarde gevonden is of er niets meer over is.

Hoeveel vergelijkingen heeft binair zoeken nodig?

Hoogstens ⌊log₂ n⌋ + 1 voor een lijst van n waarden: 6 voor 40, 10 voor 1.000, 20 voor een miljoen. Elke vergelijking halveert wat er over is.

Waarom heeft binair zoeken een gesorteerde lijst nodig?

Omdat alleen in een gesorteerde lijst één vergelijking je vertelt aan welke kant de gezochte waarde staat. In een ongesorteerde lijst zegt een kleinere waarde in het midden niets over waar de gezochte waarde staat, dus kan er niets worden uitgesloten.

Welke waarde vindt het als er dubbele waarden zijn?

Een willekeurige ervan, afhankelijk van waar de middens vallen. Varianten die na een treffer links of rechts verder zoeken, vinden de eerste of de laatste.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het zoeken draait in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor