Den største forskjellen mellom lineær søk og binær søk er at binær søk tar mindre tid å søke et element fra den sorterte listen over elementer. Så det er utledet at effektiviteten av binær søkemetode er større enn lineær søk.
En annen forskjell mellom de to er at det er en forutsetning for binær søk, det vil si at elementene må sorteres mens det er lineært søk, er det ingen slik forutsetning. Selv om begge søkemetoder bruker forskjellige teknikker som diskuteres nedenfor.
Sammenligningstabel
| Grunnlag for sammenligning | Lineær søk | Binært søk |
|---|---|---|
| Tidskompleksitet | PÅ) | O (log 2 N) |
| Beste saken tid | Første element O (1) | Senterelement O (1) |
| Forutsetning for en matrise | Ingen påkrevd | Array må være i rekkefølge |
| Verste tilfelle for N antall elementer | N sammenligninger er påkrevd | Kan konkludere etter bare logg 2 N sammenligninger |
| Kan implementeres på | Array og koblet liste | Kan ikke implementeres direkte på koblet liste |
| Sett inn operasjonen | Enkelt satt inn på slutten av listen | Krev behandling for å sette inn på riktig sted for å opprettholde en sortert liste. |
| Algoritmetype | Iterativ i naturen | Fordel og erobre i naturen |
| nytten | Enkel å bruke og ikke behov for noen bestilte elementer. | Uansett er vanskelig algoritme og elementer organisert i rekkefølge. |
| Linjer av kode | Mindre | Mer |
Definisjon av lineær søk
I et lineært søk blir hvert element i en gruppe hentet en etter en i en logisk rekkefølge og kontrollert om det er ønsket element eller ikke. Et søk vil ikke lykkes hvis alle elementene er tilgjengelige, og det ønskede elementet er ikke funnet. I verste fall kan antallet av et gjennomsnittssak vi må skanne halvparten av størrelsen på arrayet (n / 2).
Derfor kan lineær søk defineres som teknikken som krysser arrayet i rekkefølge for å finne det oppgitte elementet. Programmet som er gitt nedenfor illustrerer søket av et element i arrayet ved hjelp av søk.
Effektivitet av lineær søk
Tidsforbruket eller antall sammenligninger som gjøres ved å søke etter en plate i et søkebord, bestemmer effektiviteten av teknikken. Hvis den ønskede posten er til stede i søkestabellens første posisjon, blir det bare gjort en sammenligning. Når den ønskede posten er den siste, må n sammenlignes med. Hvis posten skal presentere et sted i søketabellen, vil gjennomsnittet i gjennomsnitt være (n + 1/2). Den verste virkningsgraden av denne teknikken er O (n) står for rekkefølgen for utførelse.
C Program for å søke et element med lineær søketeknikk.
#include #include void main () {int a [100], n, i, element, loc = -1; clrscr (); printf ("\ nSkriv antall elementer:"); scanf ("% d", & n); printf ("Skriv inn tallene: \ n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", og en [i]); } printf ("\ nTast nummeret som skal søges:"); scanf ("% d", og element); for (i = 0; i = 0) {printf ("\ n% d er funnet i posisjon% d:", element, loc + 1); } else {printf ("\ n Item eksisterer ikke"); } getch (); } Definisjon av binær søk
Binært søk er en ekstremt effektiv algoritme. Denne søketeknikken forbruker mindre tid i å søke det oppgitte elementet i minst mulige sammenligninger. For å gjøre binært søk, må vi først sortere arrayelementene.
Logikken bak denne teknikken er gitt nedenfor:
- Finn først midtelementet i arrayet.
- Mellomelementet i arrayet er sammenlignet med elementet som skal søges.
Det kan tre tilfeller oppstå:
- Hvis elementet er det nødvendige elementet, er søket vellykket.
- Når elementet er mindre enn ønsket element, så søk bare den første halvdelen av arrayet.
- Hvis den er større enn ønsket element, så søk i den andre halvdelen av arrayet.
Gjenta de samme trinnene til et element er funnet eller eksos i søkeområdet. I denne algoritmen reduseres søkeområdet hver gang. Derfor er antall sammenligninger mest log (N + 1). Som et resultat er det en effektiv algoritme sammenlignet med lineær søk, men arrayet må sorteres før du gjør binærsøk.
C Program for å finne et element med binær søketeknikk.
#include void main () {int jeg, beg, slutt, midten, n, søk, array [100]; printf ("Skriv inn elementet \ n"); scanf ( "% d", og n); printf ("Skriv inn% d tallene \ n", n); for (i = 0; i <n; i ++) scanf ("% d", og array [i]); printf ("Skriv inn nummer som skal søkes \ n"); scanf ("% d", og søk); Beg = 0; ende = n - 1; midt = (beg + ende) / 2; mens (beg <= ende) {hvis (array [middle] end) printf ("Søket mislykkes!% d er ikke tilstede i listen. \ n", søk); getch (); } Viktige forskjeller mellom lineær søk og binær søk
- Lineær søk er iterativ i naturen og bruker sekvensiell tilnærming. På den annen side utfører binære søk divisjon og erobre tilnærming.
- Tidskompleksiteten til lineær søk er O (N) mens binær søk har O (log 2 N).
- Den beste saken tid i lineær søk er for det første elementet, dvs. O (1). I motsetning til, i binær søk, er det for mellomelementet, dvs. O (1).
- I det lineære søket er verste fallet for å søke et element N-sammenligning. I motsetning er det log 2 N antall sammenligning for binær søk.
- Linjært søk kan implementeres i en rekkefølge så vel som i koblet liste, mens binært søk ikke kan implementeres direkte på koblet liste.
- Som vi vet Binært søk krever det sorterte oppsettet som er grunnen. Det krever behandling å sette inn på sitt rette sted for å opprettholde en sortert liste. Tvert imot krever lineært søk ikke sorterte elementer, slik at elementene enkelt settes inn på slutten av listen.
- Linjært søk er enkelt å bruke, og det er ikke behov for noen bestilte elementer. På den annen side er binær søkealgoritme imidlertid vanskelig, og elementene er nødvendigvis ordnet i rekkefølge.
Konklusjon
Både lineære og binære søkealgoritmer kan være nyttige avhengig av applikasjonen. Når en matrise er datastrukturen og elementene er ordnet i sortert rekkefølge, er binær søk foretrukket for rask søking. Hvis koblet liste er datastrukturen, uansett hvordan elementene er ordnet, blir lineært søk vedtatt på grunn av utilgjengelighet av direkte implementering av binær søkealgoritme.
Den typiske binære søkealgoritmen kan ikke brukes til koblet liste fordi koblet liste er dynamisk i naturen og det er ikke kjent hvor mellomelementet faktisk er tildelt. Derfor er det et krav om å designe variasjonen av binærsøkalgoritmen som kan fungere på koblet liste også fordi binærsøkingen er raskere i utførelse enn et lineært søk.
