Binêre soektog vs lineêre soektog
Lineêre soektog, ook bekend as die opeenvolgende soektog, is die eenvoudigste soekalgoritme. Dit soek na 'n gespesifiseerde waarde in 'n lys deur elke element in die lys na te gaan. Binêre soektog is ook 'n metode wat gebruik word om 'n gespesifiseerde waarde in 'n gesorteerde lys op te spoor. Binêre soekmetode halveer die aantal elemente wat nagegaan is (in elke iterasie), wat die tyd wat dit neem om die gegewe item in die lys op te spoor verminder.
Wat is Lineêre Soek?
Lineêre soektog is die eenvoudigste soekmetode, wat elke element in 'n lys opeenvolgend nagaan totdat dit 'n gespesifiseerde element vind. Die invoer na die lineêre soekmetode is 'n ry (soos 'n skikking, versameling of 'n string) en die item wat gesoek moet word. Die uitvoer is waar as die gespesifiseerde item binne die verskafde volgorde is of vals as dit nie in die volgorde is nie. Aangesien hierdie metode elke item in die lys nagaan totdat die gespesifiseerde item gevind word, sal dit in die ergste geval deur al die elemente in die lys gaan voordat dit die vereiste element vind. Die kompleksiteit van lineêre soektog is o(n). Daarom word dit as te stadig beskou om gebruik te word wanneer elemente in groot lyste gesoek word. Maar dit is baie eenvoudig en makliker om te implementeer.
Wat is Binêre Soek?
Binêre soektog is ook 'n metode wat gebruik word om 'n gespesifiseerde item in 'n gesorteerde lys op te spoor. Hierdie metode begin deur die gesoekte element te vergelyk met die elemente in die middel van die lys. As die vergelyking bepaal dat die twee elemente gelyk is, stop die metode en gee die posisie van die element terug. As die gesoekte element groter is as die middelste element, begin dit die metode weer deur slegs die onderste helfte van die gesorteerde lys te gebruik. As die gesoekte element minder as die middelste element is, begin dit die metode weer deur slegs die boonste helfte van die gesorteerde lys te gebruik. As die gesoekte element nie binne die lys is nie, sal die metode 'n unieke waarde gee wat dit aandui. Daarom halveer die binêre soekmetode die aantal elemente wat vergelyk word (in elke iterasie), afhangende van die resultaat van die vergelyking. Gevolglik loop binêre soektog in logaritmiese tyd wat lei tot o(log n) gemiddelde gevalprestasie.
Wat is die verskil tussen Binêre Soek en Lineêre Soek?
Selfs al is beide lineêre soektog en binêre soek soekmetodes, het hulle verskeie verskille. Terwyl binêre soektog op gesorteerde lyste werk, kan lynsoektog ook op ongesorteerde lyste werk. Om 'n lys te sorteer het gewoonlik 'n gemiddelde saakkompleksiteit van n log n. lineêre soektog is eenvoudig en eenvoudig om te implementeer as die binêre soektog. Maar, lineêre soektog is te stadig om met groot lyste gebruik te word as gevolg van sy o(n) gemiddelde gevalprestasie. Aan die ander kant word binêre soektog beskou as 'n meer doeltreffende metode wat met groot lyste gebruik kan word. Maar die implementering van die binêre soektog kan nogal moeilik wees en 'n studie het getoon dat die akkurate kode vir binêre soektog in slegs vyf uit twintig boeke gevind kan word.
