Inhoudsopgave:
Definitie - Wat betekent binair zoeken?
Een binair zoekalgoritme wordt gebruikt om de positie van een specifieke waarde in een gesorteerde array te vinden. Werkend met het principe van verdeel en heers, kan dit zoekalgoritme vrij snel zijn, maar de waarschuwing is dat de gegevens in een gesorteerde vorm moeten zijn. Het werkt door het zoeken in het midden van de array te starten en naar beneden te gaan in de eerste onderste of bovenste helft van de reeks. Als de mediaanwaarde lager is dan de doelwaarde, betekent dit dat de zoekopdracht hoger moet gaan, zo niet, dan moet deze naar het aflopende gedeelte van de array kijken.
Een binaire zoekopdracht is ook bekend als een zoekopdracht met half interval of logaritmische zoekopdracht.
Techopedia legt Binary Search uit
Een binaire zoekopdracht is een snelle en efficiënte methode om een specifieke doelwaarde te vinden uit een reeks geordende items. Door in het midden van de gesorteerde lijst te beginnen, kan het de zoekruimte effectief doormidden snijden door te bepalen of de lijst moet worden verhoogd of verlaagd op basis van de mediaanwaarde in vergelijking met de doelwaarde.
Met een doelwaarde van 8 en een zoekruimte van 1 tot en met 11:
- De mediaan / middenwaarde wordt gevonden en de aanwijzer wordt daar ingesteld, wat in dit geval 6 is.
- Het doelwit van 8 wordt vergeleken met 6. Aangezien 6 kleiner is dan 8, moet het doelwit zich in de hogere helft bevinden.
- De aanwijzer wordt verplaatst naar de volgende waarde (7) en vergeleken met het doel. Het is kleiner, daarom gaat de aanwijzer naar de volgende hogere waarde.
- De aanwijzer staat nu op 8. Als u dit vergelijkt met het doel, is dit een exacte overeenkomst, daarom is het doel gevonden.
Met binair zoeken hoefde het doelwit slechts met drie waarden te worden vergeleken. In vergelijking met een lineaire zoekopdracht, zou het zijn begonnen vanaf de allereerste waarde en omhoog zijn gegaan, waarbij het doel moest worden vergeleken met acht waarden. Een binaire zoekopdracht is alleen mogelijk met een geordende set gegevens; als de gegevens willekeurig zijn gerangschikt, levert een lineaire zoekopdracht altijd resultaten op, terwijl een binaire zoekopdracht waarschijnlijk vastloopt in een oneindige lus.
