Indhold

• Sammenligningstabel
• Definition af lineær søgning
• Definition af binær søgning
• Konklusion

Lineær søgning og binær søgning er de to metoder, der bruges i matriser til søger elementerne. Søgning er en proces med at finde et element på listen over elementer, der er gemt i enhver rækkefølge eller tilfældigt.

Den største forskel mellem lineær søgning og binær søgning er, at binær søgning tager mindre tid på at søge i et element fra den sorterede liste over elementer. Så det udledes, 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 den binære søgning, dvs. elementerne skal være sorterede mens der i lineær søgning ikke er nogen sådan forudsætning. Selvom begge søgemetoder bruger forskellige teknikker, der diskuteres nedenfor.

1. Sammenligningstabel
2. Definition
3. Vigtige forskelle
4. Konklusion

Sammenligningstabel

Grundlag for sammenligning	Lineær søgning	Binær søgning
Tidskompleksitet	PÅ)	O (log 2 N)
Bedste sagstid	Første element O (1)	Centerelement O (1)
Forudsætning for en matrix	Ingen krævet	Array skal være i sorteret rækkefølge
Værste tilfælde for N antal elementer	Der kræves ingen sammenligninger	Kan afslutte efter kun log2N sammenligninger
Kan implementeres på	Array og linket liste	Kan ikke implementeres direkte på den linkede liste
Indsæt betjening	Isæt let i slutningen af ​​listen	Kræver behandling for at indsætte på det rigtige sted for at vedligeholde en sorteret liste.
Algoritmetype	Iterativ karakter	Del og erobre i naturen
nytten	Let at bruge og ikke behov for bestilte elementer.	Under alle omstændigheder bør vanskelige algoritmer og elementer organiseres i rækkefølge.
Kodelinjer	Mindre	Mere

Definition af lineær søgning

I en lineær søgning hentes hvert element i en matrix en ad gangen i en logisk rækkefølge og kontrolleres, om det er det ønskede element eller ej. En søgning vil ikke være vellykket, hvis der er adgang til alle elementerne, og det ønskede element ikke findes. I værste fald er antallet af gennemsnitlige sager muligvis nødt til at scanne halvdelen af ​​størrelsen på matrixen (n / 2).

Derfor kan lineær søgning defineres som den teknik, der gennemgår rækkefølgen sekventielt for at lokalisere det givne emne. Programmet givet nedenfor illustrerer søgningen efter et element i matrixen ved hjælp af søgning.

Effektivitet af lineær søgning

Tidsforbruget eller antallet af sammenligninger, der er foretaget ved søgning i en post i en søgetabel, bestemmer teknikens effektivitet. Hvis den ønskede post er til stede i den første position i søgetabellen, foretages der kun en sammenligning. Når den ønskede post er den sidste, skal der sammenlignes n. Hvis posten skal vises et sted i søgetabellen i gennemsnit, er antallet af sammenligninger (n + 1/2). Effektiviteten af ​​denne teknik i værste tilfælde er O (n) står for rækkefølgen af ​​udførelse.

C-program at søge i et element med lineær søgeteknik.

#omfatte #omfatte void main () {int a, n, i, item, loc = -1; clrscr (); f (" nTast antallet af elementer:"); scanf ("% d", & n); f ("Indtast numrene: n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nIndtast det nummer, der skal søges:"); scanf ("% d", & vare); for (i = 0; i <= n-1; i ++) {if (vare == a) {loc = i; pause; }} hvis (loc> = 0) {f (" n% d findes i position% d:", vare, loc + 1); } andet {f (" n Varen findes ikke"); } getch (); }

Definition af binær søgning

Binær søgning er en ekstremt effektiv algoritme. Denne søgeteknik forbruger mindre tid på at søge efter det givne emne i mindst mulige sammenligninger. For at udføre den binære søgning skal vi først sortere arrayelementerne.

Logikken bag denne teknik er givet nedenfor:

• Find først det midterste element i matrixen.
• Det midterste element i arrayet sammenlignes med det element, der skal søges.

Der er tre tilfælde, der kunne opstå:

1. Hvis elementet er det krævede element, er søgningen vellykket.
2. Når elementet er mindre end det ønskede emne, skal du kun søge i den første halvdel af matrixen.
3. Hvis det er større end det ønskede element, skal du søge i den anden halvdel af matrixen.

Gentag de samme trin, indtil et element findes eller udtømmes i søgeområdet. I denne algoritme reduceres hver gang søgeområdet. 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 udfører den binære søgning.

C-program for at finde et element med binær søgningsteknik.

#omfatte void main () {int i, beg, slut, midten, n, søgning, matrix; f ("Indtast antallet af element n"); scanf ( "% d", & n); f ("Indtast% d-numrene n", n); for (i = 0; i <n; i ++) scanf ("% d", & array); f ("Indtast nummer, der skal søges n"); scanf ("% d", & søgning); beg = 0; ende = n - 1; midt = (beg + ende) / 2; mens (beg <= slut) {if (array <søgning) beg = midt + 1; ellers hvis (array == søgning) {f ("Søgning er vellykket. n% d fundet på placering% d. n", søgning, midterste + 1); pause; } andet slut = midt - 1; midt = (beg + ende) / 2; } hvis (beg> slut) f ("Søgning er ikke succesrig!% d er ikke til stede på listen. n", søg); getch (); }

1. Lineær søgning er iterativ og bruger sekventiel tilgang. På den anden side implementerer binær søgning opdele og erobre tilgang.
2. Tidskompleksiteten for lineær søgning er O (N), mens binær søgning har O (log₂N).
3. Det bedste tilfælde i lineær søgning er for det første element, dvs. O (1). I binær søgning er det mod det midterste element, dvs. O (1).
4. I den lineære søgning er det værste tilfælde for søgning i et element N antal sammenligninger. I modsætning hertil er det log₂N antal sammenligninger til binær søgning.
5. 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å den linkede liste.
6. Som vi ved, kræver binær søgning det sorterede array, som er grunden. Det kræver behandling at indsætte på det rigtige sted for at opretholde en sorteret liste. Tværtimod kræver lineær søgning ikke sorterede elementer, så elementer let indsættes i slutningen af ​​listen.
7. Lineær søgning er let at bruge, og der er ikke behov for ordnede elementer. På den anden side er binær søgealgoritme 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 en matrix er datastrukturen og elementerne er arrangeret i sorteret rækkefølge, foretrækkes binær søgning til hurtigsøger. Hvis den tilknyttede 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øgealgoritme.

Den typiske binære søgealgoritme kan ikke bruges til den tilknyttede liste, fordi den tilknyttede liste er dynamisk og det vides ikke, hvor det midterste element faktisk er tildelt. Derfor er der et krav om at designe variationen af ​​den binære søgealgoritme, der også kan arbejde på en linket liste, fordi den binære søgning er hurtigere i udførelse end en lineær søgning.