Lineaire zoekopdrachten en binaire zoekopdrachten zijn veelgebruikte algoritmen om elementen binnen een lijst te vinden. Het begrijpen van het verwachte aantal vergelijkingen dat elk algoritme maakt kan helpen bij het kiezen van de meest efficiënte methode voor specifieke situaties. Dit artikel vergelijkt de verwachte vergelijkingen in lineaire versus binaire zoekmethoden.

Lineair zoeken

Lineaire zoekopdracht controleert elk element in de lijst achtereenvolgens totdat het het doel vindt of het einde bereikt. Het verwachte aantal vergelijkingen hangt af van de vraag of het doel aanwezig is en de positie ervan in de lijst.

Als de lijst elementen bevat n en het streefcijfer waarschijnlijk op elke positie zal liggen, is het verwachte aantal vergelijkingen:

Verwachte vergelijkingen = (n + 1) / 2

Dit komt omdat gemiddeld de zoekopdracht het doel halverwege de lijst zal vinden.

Binaire zoekopdracht

Binaire zoekopdrachten werken op gesorteerde lijsten door het zoekinterval herhaaldelijk in tweeën te delen. De efficiëntie ervan hangt af van de lijstgrootte en de positie van het doel.

In het beste geval ligt het doel in het midden, waarbij slechts één vergelijking vereist is. In het ergste geval is het ongeveer log2 n vergelijkingen.

Uitgaande van de waarschijnlijkheid dat het streefcijfer op elke positie zal liggen, is het verwachte aantal vergelijkingen ruwweg:

Verwachte vergelijkingen ≈ log2 n

Vergelijkingsoverzicht

  • Lineaire zoekopdracht heeft een verwachte vergelijkingstelling van (n + 1) / 2.
  • Binaire zoekopdracht heeft een verwachte vergelijkingstelling van ongeveer log2 n.
  • Binaire zoekopdracht vereist over het algemeen minder vergelijkingen voor grote lijsten.
  • Lineaire zoekopdrachten kunnen de voorkeur hebben voor kleine of ongesorteerde lijsten.