Binair zoeken

Probleem 2:

Binair zoeken, ook wel bekend als binaire zoekmethode of dichotoom zoeken, is een efficiënte methode om een specifiek element te vinden in een gesorteerde lijst of array. Het werkt als volgt:

1. Begin in het midden van de gesorteerde lijst.

2. Vergelijk het gezochte element met het element in het midden van de lijst.

3. Als het gezochte element gelijk is aan het element in het midden, is de zoekopdracht voltooid.

4. Als het gezochte element kleiner is dan het element in het midden, zoek dan in de eerste helft van de lijst.

5. Als het gezochte element groter is dan het element in het midden, zoek dan in de tweede helft van de lijst.

6. Herhaal de bovenstaande stappen totdat het gezochte element is gevonden of totdat de lijst niet meer kan worden verdeeld.

Binair zoeken maakt gebruik van de eigenschap van een gesorteerde lijst waarbij het mogelijk is om snel te bepalen in welke helft van de lijst het gezochte element zich bevindt. Hierdoor kan het gezochte element efficiënt worden gevonden met een tijdscomplexiteit van O(log n), waarbij n het aantal elementen in de lijst is. Dit maakt binair zoeken veel sneller dan lineair zoeken voor grote gesorteerde lijsten.

Passen we de binaire zoekmethode hier toe, dan krijgen we onderstaand algoritme in pseudocode:

We nummeren de kaarten van hoog naar laag met de cijfer 1 --> 9

Bereken gok = (hoogste cijfer + laagste cijfer)/2

Zolang kaart met cijfer gok is niet schoppen 6:

    Als koort met cijfer gok > schoppen 6:

                    Gooi deze kaart en alle kaarten kleiner weg

    Anders

                   Gooi deze kaart en alle kaarten groter weg

    Bereken gok = (hoogste cijfer +  laagste cijfer)/2

Het binair zoekalgoritme is zeer goed om in grote gesorteerde bestanden naar een gegeven te zoeken.  Het behoort tot de verdeel en heers algoritmes omdat je telkens een deel van je "data" weggooit en zo je groep kleiner maakt.

Zo heb je voor een lijst met één miljoen gegevens '(maximaal) slechts 20 stappen nodig om dit gegeven te vinden.

Telkens we dit met een factor 1000 verhogen, komen er maar 10 stappen bij.