Den største forskel mellem lineær søgning og binær søgning er, at binær søgning tager mindre tid at søge et element fra den sorterede liste over elementer. Så det er udledt, at effektiviteten af binær søgemetode er større end lineær søgning.
En anden forskel mellem de to er, at der er en forudsætning for binær søgning, dvs. elementerne skal sorteres, mens der i lineær søgning ikke findes en sådan forudsætning. Selvom begge søgemetoder bruger forskellige teknikker, der diskuteres nedenfor.
Sammenligningstabel
| Grundlag for sammenligning | Lineær søgning | Binær søgning |
|---|---|---|
| Tidskompleksitet | PÅ) | O (log 2 N) |
| Bedste case tid | Første element O (1) | Center Element O (1) |
| Forudsætning for en matrix | Ingen påkrævet | Array skal være i rækkefølge |
| Værste tilfælde for N antal elementer | N sammenligninger er påkrævet | Kan konkludere efter kun log 2 N sammenligninger |
| Kan implementeres på | Array og Linked List | Kan ikke implementeres direkte på linket liste |
| Indsæt operation | Nemt indsat i slutningen af listen | Kræv behandling for at indsætte på det rette sted for at opretholde en sorteret liste. |
| Algoritm type | Iterativ i naturen | Opdele og erobre i naturen |
| nytten | Nem at bruge og ikke behov for nogen bestilte elementer. | Under alle omstændigheder bør det være organiseret i orden, at det er vanskelig at algoritme og elementer. |
| Linjer af kode | Mindre | Mere |
Definition af lineær søgning
I en lineær søgning hentes hvert element i et array en efter en i en logisk rækkefølge og kontrolleres, om det er ønsket element eller ej. En søgning bliver mislykket, hvis alle elementer er tilgængelige, og det ønskede element er ikke fundet. I værste fald er antallet af et gennemsnitligt tilfælde muligvis nødvendigt at scanne halvdelen af størrelsen af arrayet (n / 2).
Derfor kan lineær søgning defineres som den teknik, der krydser arrayet sekventielt for at finde den givne genstand. Programmet nedenfor viser illustrationen af et element i arrayet ved hjælp af søgning.
Effektivitet af lineær søgning
Tidsforbruget eller antallet af sammenligninger, der gøres ved søgning i en post i et søgebord, bestemmer effektiviteten af teknikken. Hvis den ønskede post er til stede i søgelysets første position, foretages der kun en sammenligning. Når den ønskede rekord er den sidste, skal der foretages n sammenligninger. Hvis posten skal præsentere et sted i søgetabellen, vil der gennemsnitligt være sammenligninger (n + 1/2). Den værste tilfælde effektivitet af denne teknik er O (n) står for rækkefølgen af udførelse.
C Program for at søge et element med lineær søgeteknik.
#include #include void main () {int a [100], n, i, punkt, loc = -1; clrscr (); printf ("\ nOpfør antallet af elementer:"); scanf ("% d", & n); printf ("Indtast tallene: \ n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nTryk det nummer, der skal søges:"); scanf ("% d", og element); for (i = 0; i = 0) {printf ("\ n% d findes i position% d:", punkt, loc + 1); } else {printf ("\ n Item eksisterer ikke"); } getch (); } Definition af binær søgning
Binær søgning er en ekstremt effektiv algoritme. Denne søgeteknik bruger mindre tid i at søge det givne emne i mindst mulige sammenligninger. For at gøre binær søgning skal vi først sortere arrayelementerne.
Logikken bag denne teknik er angivet nedenfor:
- Find først midtelementet i arrayet.
- Mellemelementet i arrayet sammenlignes med det element, der skal søges.
Der kan opstå tre tilfælde:
- Hvis elementet er det nødvendige element, er søgningen vellykket.
- Når elementet er mindre end det ønskede emne, så søg kun den første halvdel af arrayet.
- Hvis det er større end det ønskede element, så søg i anden halvdel af arrayet.
Gentag de samme trin, indtil et element er fundet eller udstødninger i søgeområdet. I denne algoritme reduceres søgeområdet hver gang. Derfor er antallet af sammenligninger højst log (N + 1). Som et resultat er det en effektiv algoritme sammenlignet med lineær søgning, men arrayet skal sorteres, inden du foretager binær søgning.
C Program for at finde et element med binær søgeteknik.
#include void main () {int jeg, beg, ende, midten, n, søgning, array [100]; printf ("Indtast antal elementer \ n"); scanf ( "% d", & n); printf ("Indtast% d numrene \ n", n); for (i = 0; i <n; i ++) scanf ("% d", og array [i]); printf ("Indtast nummer, der skal søges \ n"); scanf ("% d", og søgning); beg = 0; ende = n - 1; middle = (beg + ende) / 2; mens (beg <= ende) {hvis (array [middle] end) printf ("Søgningen mislykkes!% d er ikke til stede i listen. \ n", søgning); getch (); } Nøgleforskelle mellem lineær søgning og binær søgning
- Lineær søgning er iterativ i naturen og bruger sekventiel tilgang. På den anden side gennemfører binære søgninger opdeling og erobring af tilgang.
- Tidskompleksiteten af lineær søgning er O (N), mens binær søgning har O (log 2 N).
- Den bedste sagstid i lineær søgning er for det første element, dvs. O (1). Modsat i binær søgning er det for middelelementet, dvs. O (1).
- I den lineære søgning er det værste tilfælde at søge et element N-sammenligning. Derimod er det log 2 N antal sammenligning for binær søgning.
- Lineær søgning kan implementeres i en matrix såvel som i en linket liste, mens binær søgning ikke kan implementeres direkte på linket liste.
- Som vi ved Binær søgning kræver den sorterede matrix, der er grunden. Det kræver, at behandlingen indsættes på det rette sted for at opretholde en sorteret liste. Tværtimod kræver lineær søgning ikke sorterede elementer, så elementer er let indsat i slutningen af listen.
- Lineær søgning er let at bruge, og der er ikke behov for nogen ordnede elementer. På den anden side er binær søgning algoritme imidlertid vanskelig, og elementer er nødvendigvis arrangeret i rækkefølge.
Konklusion
Både lineære og binære søgealgoritmer kan være nyttige afhængigt af applikationen. Når et array er datastrukturen og elementerne er arrangeret i rækkefølge, så foretrækkes binær søgning til hurtig søgning. Hvis linket liste er datastrukturen uanset hvordan elementerne er arrangeret, vedtages lineær søgning på grund af utilgængelighed af direkte implementering af binær søgning algoritme.
Den typiske binære søgealgoritme kan ikke anvendes til den tilknyttede liste, fordi linket liste er dynamisk i naturen, og det vides ikke, hvor mellemelementet faktisk er tildelt. Derfor er der et krav om at designe variationen af binærsøgningsalgoritmen, der kan arbejde på linket liste også, fordi binær søgning er hurtigere i udførelse end en lineær søgning.
